concatenate the digit of path from the root to the leaf, and sum over the concatenated numbers.
Intuition
Use DFS to find all the paths, use a num variable to store the number concatenated, then sum over num.
Approach
We use num to represent the number from the root to the current node, if the current node is a leaf node,
we add num to sum. Finally, we return sum as the result.
Complexity
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void dfs(TreeNode *root, int &sum, int &num){
if (!root) {
return;
}
num = num * 10 + root->val;
if (!root->left && !root->right){
sum += num;
}else{
dfs(root->left, sum, num);
dfs(root->right, sum, num);
}
num /= 10;
}
int sumNumbers(TreeNode* root) {
int sum = 0;
int num = 0;
dfs(root, sum, num);
return sum;
}
};
|