Problem

Given a binary tree containing digits from0-9only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path1->2->3which represents the number123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path1->2represents the number12.
The root-to-leaf path1->3represents the number13.

Return the sum = 12 + 13 =25.

做法一

    public int sumNumbers(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        helper(root, new StringBuilder(), list);
        System.out.println(list);
        int sum = 0;
        for (int num: list) sum += num;

        return sum;
    }

    private void helper(TreeNode root, StringBuilder sb, List<Integer> list) {
        if (root == null) return;

        int len = sb.length();
        sb.append(root.val);
        if (root.left == null && root.right == null) {
            if (sb.length() > 0) 
                list.add(Integer.parseInt(sb.toString()));
        }
        helper(root.left, sb, list);
        helper(root.right, sb, list);
        sb.setLength(len);
    }

做法二

    /*
        1. 只有下自上是不行的， 因为左子和右子的长度不一致，所以无法确定当前节点的长度。
        2. 因此只能自上而下传递presum， 然后再从下而上返回

                            o
                    o                   o
                        o
    */
    public int sumNumbers(TreeNode root) {
        return sum(root, 0);
    }

    private int sum(TreeNode root, int preSum) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return preSum * 10 + root.val;
        return sum(root.left, preSum * 10 + root.val) + sum(root.right, preSum * 10 + root.val);
    }