129. Sum Root to Leaf Numbers.md

Solution1

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

Solution2

class Solution {
    public int sumNumbers(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        int[] res = {0};
        if (root == null) {
            return res[0];
        }
        dfs(root, sb, res);
        return res[0];
    }
    private void dfs(TreeNode root, StringBuilder sb, int[] res) {
        if (root == null)   return;
        sb.append(root.val);
        if (root.left == null && root.right == null) {
            res[0] += Integer.valueOf(new String(new StringBuilder(sb)));
        } 
        if (root.left != null) {
            dfs(root.left, sb, res);
        }
        if (root.right != null) {
            dfs(root.right, sb, res);
        }
        sb = sb.deleteCharAt(sb.length() - 1);
    }
}

note

• dfs. accumulating sum
• Solution2 is my original answer which uses stringbuilder and backtracking. Initially, I use a global variable res to record the result, but it caused problem because when oj calls the class multiple times, if the first example results 25 and the seond time the class gets called, the res will be 25 as starting point instead of 0. So, I changed res to be an array of length 1 and pass this to the function which works.