Binary Tree Path Sum

这个题有一个大坑
一般dfs的终止条件是root == null
但是这个题目里面如果走到leaf之后，它的左右child会各把答案加入一次，就错了
所以必须在leaf就终止 就是说root.left == null && root.right == null

Version #2 在当前层加入当前node
有一个bug就是当leaf节点提前return的时候必须要backtracking
每一次return到上一层都要backtracking!!!

public class Solution {
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        // Write your code here
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) return result;
        helper(root, 0, target, new ArrayList<Integer>(), result);
        return result;
    }
    //add current node to the path, add current value to the sum
    private void helper(TreeNode root, int sum, int target, List<Integer> path, List<List<Integer>> result) {
        if (root == null) return;
        path.add(root.val);
        sum += root.val;
        if (root.left == null && root.right == null) {
            if (sum == target) result.add(new ArrayList<Integer>(path));
            path.remove(path.size() - 1);
            return;
        }
        helper(root.left, sum, target, path, result);
        helper(root.right, sum, target, path, result);
        path.remove(path.size() - 1);
    }
}



Version #1 在上一层就加左右的node进入path以及加入sum
public class Solution {
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        // Write your code here
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        List<Integer> path = new ArrayList<>();
        path.add(root.val);
        int sum = root.val;
        helper(path, sum, root, target, result);
        return result;
    }
 
    public void helper(
        List<Integer> path,
        int sum,
        TreeNode root,
        int target,
        List<List<Integer>> result
        ) {
            if (root.left == null && root.right == null) {
                if (sum == target) {
                    result.add(new ArrayList<Integer>(path));
                }
            }
         
            if (root.left != null) {
                path.add(root.left.val);
                helper(path, sum + root.left.val, root.left, target, result);
                path.remove(path.size() - 1);
            }
         
            if (root.right != null) {
                path.add(root.right.val);
                helper(path, sum + root.right.val, root.right, target, result);
                path.remove(path.size() - 1);
            }
    }
}