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 1: DFS, when reach to leaf, add the result.
public class Solution {
public int sumNumbers(TreeNode root) {
int[] res=new int[1];
dfs(root,0,res);
return res[0];
}
private void dfs(TreeNode x, int num, int[] res) {
if (x==null) return;
num=num*10+x.val;
if (x.left==null && x.right==null) res[0]+=num;
dfs(x.left,num,res);
dfs(x.right,num,res);
}
}
没有评论:
发表评论