Binary Tree Paths

Question:

Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target.

A valid path is from root node to any of the leaf nodes.

Example
Given a binary tree, and target = 5:

     1
    / \
   2   4
  / \
 2   3


return

[
  [1, 2, 2],
  [1, 4]
]

Lesson Learned

• reference的问题说几次也不嫌多。最初只定义了一个全局变量path来存储满足sum = target的路径，然后改变路径和相对应的sum的值得出路径，但是只得到了两个空arraylist，原因是当遍历完时，path指向的地址里面装的是空的arraylist。而加入list里的恰恰是path的地址，所以返回两个空的arraylist[[],[]].
  • 解决方法是定义一个局部变量，每次当满足条件的时候，将会变化的全局变量复制到新的局部变量中，每次全局变量修改的时候都对这个每次都新构建的局部变量没有影响

Code:

1st Attempt;

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    private List<List<Integer>> lists = new ArrayList<List<Integer>>();
    private List<Integer> path =  new ArrayList<Integer>();
    private int sum;

    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        sum = 0;
        helper(root, target);
        return lists;
    }

    private void helper(TreeNode root, int target) {
        // Write your code here`
        if (root == null) {
            return;
        }

        sum += root.val;
        path.add(root.val);

        if (root.left == null && root.right == null && sum == target) {
            // compare sum & target
            // add 的是path的reference
            List<Integer> l = new ArrayList<Integer>();
            for (int i = 0; i < path.size(); i++) {
                l.add(path.get(i));
            }
            lists.add(l);
        }
        helper(root.left, target);
        helper(root.right, target);
        sum -= path.get(path.size() - 1);
        path.remove(path.size() - 1);

    }
}

Second Attempt: