Given a binary tree containing digits from
0-9
only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path
1->2->3
which represents the number 123
.
Find the total sum of all root-to-leaf numbers.
For example,
1 / \ 2 3
The root-to-leaf path
The root-to-leaf path
1->2
represents the number 12
.The root-to-leaf path
1->3
represents the number 13
.
Return the sum = 12 + 13 =
25
.
Solution:O(n)
public class Solution {public int sumNumbers(TreeNode root) {
if(root == null)
return 0;
if(root.left == null && root.right == null)
return root.val;
int sum = 0;
if(root.left!=null){
root.left.val += (root.val *10);
sum+=sumNumbers(root.left);
}
if(root.right!=null){
root.right.val += (root.val *10);
sum+=sumNumbers(root.right);
}
return sum;
}
}
Key Concept: Recursive and save prevalue to root.
沒有留言:
張貼留言