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:
Recursion:
Recursion equation: V(root)=curSUM*10+V(left)+V(right).
Base case: root==null-> return 0, if root is leaf, return curSUM*10+root.val;
public int sumNumbers(TreeNode root) {
return helper(root,0);
}
public int helper(TreeNode root, int cur){
if(root==null) return 0;
if(root.left==null && root.right==null) return cur*10+root.val;
return helper(root.left, cur*10+root.val)+helper(root.right,cur*10+root.val);
}
No comments:
Post a Comment