Binary Tree Path Sum

题目：

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.

分析：

这是第一次用java解决binary tree的问题，dfs的方法，需要注意一点就是当你把path加入到res里面的时候，因为java所有的都是pass by value，所以需要

res.add(new ArrayList<Integer>(path) );

而直接add path这个value是不行的...

解法：

public class Solution {
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    public int getSum(List<Integer> path) {
        int sum = 0;
        for (int i = 0; i < path.size(); i++) {
            sum += path.get(i);
        }
        return sum;
    } 

    public void dfs(List<List<Integer> > res, List<Integer> path, TreeNode root, int target) {
        if (root == null) {
            return;
        }

        if (root.left == null && root.right == null) {
            if (getSum(path) == target) {
                res.add(new ArrayList<Integer>(path) );
            }
            return;
        }

        if (root.left != null) {
            path.add(root.left.val);
            dfs(res, path, root.left, target);
            path.remove(path.size() - 1);
        }

        if (root.right != null) {
            path.add(root.right.val);
            dfs(res, path, root.right, target);
            path.remove(path.size() - 1);
        }
    } 

    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        // Write your code here

        List<List<Integer> > res = new ArrayList<List<Integer> >();
        if (root == null) {
            return res;
        }

        List<Integer> path = new ArrayList<Integer>();
        path.add(root.val);
        dfs(res, path, root, target);
        return res;
    }
}