129. Sum Root to Leaf Numbers

//O(n) time and space
class Solution {
    int sum = 0;
    public int sumNumbers(TreeNode root) {
        if(root==null) return 0;
        dfs(root, 0);
        return sum;
    }
    
    public void dfs(TreeNode root, int cur) {
        if(root==null) return;
        cur = cur*10 + root.val;
        if(root.left==null && root.right==null) {
            sum+=cur;
        }
        else {
            dfs(root.left, cur);
            dfs(root.right, cur);
        }
        cur-=root.val;
        cur/=10;
    }
    
}


//O(n^2) time and O(n) space
class Solution {
    public int sumNumbers(TreeNode root) {
        List<List<Integer>> result = new ArrayList();
        List<Integer> list = new ArrayList();
        backtrack(result, list, root);
        int sum = 0;
        for(List<Integer> r:result) {
            String s = "";
            for(Integer l:r) {
                s+=l;
            }
            sum+=Integer.parseInt(s);
        }
        return sum;
    }
    
    public void backtrack(List<List<Integer>> result, List<Integer> list, TreeNode root) {
        if(root==null) return;
        list.add(root.val);
        if(root.left==null && root.right==null) {
            result.add(new ArrayList(list));
        }
        else {
            backtrack(result, list, root.left);
            backtrack(result, list, root.right);
        }
        list.remove(list.size()-1);
    }
    
}