Sum Root to Leaf Numbers

Question

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.

Solution

自己是用 backtrack 來寫這題，用一個 StringBuilder 枚舉所有 root -> leaf，加完後再用 deleteCharAt。

public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }

        List<String> list = new ArrayList<String>();
        helper(root, list, new StringBuilder());
        int res = 0;
        for (String s : list) {
            res += Integer.parseInt(s);
        }

        return res;
    }

    public void helper(TreeNode t, List<String> temp, StringBuilder sb) {
        if (t == null) {
            return;
        } else if (t != null && t.left == null && t.right == null) {
            temp.add(sb.append(Integer.toString(t.val)).toString());
            sb.deleteCharAt(sb.length() - 1);
            return;
        }

        sb.append(Integer.toString(t.val));
        helper(t.left, temp, sb);
        helper(t.right, temp, sb);
        sb.deleteCharAt(sb.length() - 1);
    }

上面 code 的效率不好。參考解答的 recursion 十分漂亮，可以學一下。

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

public int sum(TreeNode n, int s){
    if (n == null) return 0;
    if (n.right == null && n.left == null) return s*10 + n.val;
    return sum(n.left, s*10 + n.val) + sum(n.right, s*10 + n.val);
}

或參考這個

public class Solution {
    int total;

    public int sumNumbers(TreeNode root) {
        total = 0;
        helper(root, 0);
        return total;
    }

    void helper(TreeNode root, int sum) {
        if (root == null) return;

        sum = sum * 10 + root.val;

        if (root.left == null && root.right == null) {
            total += sum;
            return;
        }

        helper(root.left, sum);
        helper(root.right, sum);
    }
}