129. 求根节点到叶节点数字之和

129. 求根节点到叶节点数字之和

 

 深搜,每下一层×10,直到到了叶节点才返回值,

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10  * };
11  */
12 class Solution {
13 public:
14     int DFS(TreeNode* root,int pre)
15     {
16         if(!root)
17         {
18             return 0;
19         }
20         int sum=10*pre+root->val;
21         if(!root->left && !root->right)
22         {
23             return sum;
24         }
25         return DFS(root->left,sum)+DFS(root->right,sum);
26     }
27     int sumNumbers(TreeNode* root) {
28        return DFS(root,0);
29     }
30     
31 };

 

上一篇:129. 求根节点到叶节点数字之和


下一篇:Morris遍历-空间复杂度o(1)遍历树