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`

.**Understand the problem:**

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