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 =
Understand the problem:25
.The problem asks for the sum of all root-to-leaf numbers. The problem itself is not hard to understand. Use DFS is the natural way. The only thing to note is the overflow problem, so we may use a long long to store the intermediate results.
Solution:
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { long pathSum = 0; public int sumNumbers(TreeNode root) { sumNumbersHelper(root, 0); return (int)pathSum; } private void sumNumbersHelper(TreeNode root, long curSum) { if (root == null) { return; } curSum = curSum * 10 + root.val; if (root.left == null && root.right == null) { pathSum += curSum; } sumNumbersHelper(root.left, curSum); sumNumbersHelper(root.right, curSum); } }
Update on 10/8/14:
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int sumNumbers(TreeNode root) { return sumNumbersHelper(root, 0); } private int sumNumbersHelper(TreeNode root, int preSum) { if (root == null) { return 0; } int curSum = root.val + preSum * 10; if (root.left == null && root.right == null) { return curSum; } return sumNumbersHelper(root.left, curSum) + sumNumbersHelper(root.right, curSum); } }
No comments:
Post a Comment