首页 > 代码库 > [LeetCode#129]Sum Root to Leaf Numbers
[LeetCode#129]Sum Root to Leaf Numbers
The problem:
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 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
My first analysis:
Key:
1. we search on the tree, and record all pathes in an ArrayList as return value.
2. we add the number(represented by each ArrayList) to get the final result.
possible pitfall:
We usually use sum += val to get the total sum.
However it‘s not suitable for this case, since we have already use "sub_sum * 10 + ret.get(i).get(j)" for representing current value.
You must be very carful about this!!!
My first solution:
Note: sub_sum = sub_sum * 10 + ret.get(i).get(j), not sub_sum + = sub_sum * 10 + ret.get(i).get(j)
public class Solution { public int sumNumbers(TreeNode root) { if (root == null) return 0; ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>> (); ArrayList<Integer> ans = new ArrayList<Integer>(); get_path(root, ans, ret); int sum = 0; int sub_sum = 0; for (int i = 0; i < ret.size(); i++) { for (int j = 0; j < ret.get(i).size(); j++) { sub_sum = sub_sum * 10 + ret.get(i).get(j); //not sub_sum += sub_sum * 10 + ret.get(i).get(j); } sum += sub_sum; sub_sum = 0; } return sum; } private void get_path(TreeNode cur_root, ArrayList<Integer> ans, ArrayList<ArrayList<Integer>> ret) { if (cur_root == null) return; ArrayList<Integer> cur_list = new ArrayList<Integer> (ans); cur_list.add(cur_root.val); if (cur_root.left == null && cur_root.right == null) { ret.add(cur_list); return; } get_path(cur_root.left, cur_list, ret); get_path(cur_root.right, cur_list, ret); }}
My second solution:
public class Solution { public int sumNumbers(TreeNode root) { return helper(root, 0); } private int helper(TreeNode root, int sum) { //the sum is a little misleading!!! take care! if (root == null) return 0; if (root.left == null && root.right == null) return sum * 10 + root.val; return helper(root.left, sum * 10 + root.val) + helper(root.right, sum * 10 + root.val); }}
[LeetCode#129]Sum Root to Leaf Numbers