376.Binary Tree Path Sum

1.Description(Easy)

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

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]
]

2.Code

Version 1:

public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
          List<List<Integer>> result =new ArrayList<>();
          if(root==null){
              return result;
          }
          ArrayList<Integer> path=new ArrayList<Integer>();
          path.add(root.val);
          dfs(root,result,path,target,root.val);
          return result;
    }

    public void dfs(TreeNode root,
                    List<List<Integer>> result,
                    ArrayList<Integer> path,
                    int target,
                    int sum){

        //meet leaf
        if(root.left==null && root.right==null && sum==target){
            //same meaning: result.add(new ArrayList<Integer>(path));
            ArrayList<Integer> newlist=new ArrayList<Integer>();
            for(int i=0;i<path.size();i++){
                newlist.add(path.get(i));
            }
            result.add(newlist);
            return;
        }

        //go left
        if(root.left!=null){
            path.add(root.left.val);
            dfs(root.left,result,path,target,sum+root.left.val);
            path.remove(path.size()-1);

        }
        //go right
        if(root.right!=null){
            path.add(root.right.val);
            dfs(root.right,result,path,target,sum+root.right.val);
            path.remove(path.size()-1);
        }                
    }

Version 2:https://jingjingshao.gitbooks.io/data-structure-and-algorithm-analysis/content/Tree/binary_tree_path_problem.html

    private List<List<Integer>> lists = new ArrayList<List<Integer>>();
    private List<Integer> path =  new ArrayList<Integer>();
    private int sum;

    public List<List<Integer>> binaryTreePathSum2(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
            // the thing of add is the reference of path.
            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);

    }