Binary Tree Path Sum

public class Solution {
    //
     private class ResultType{
        public int sum;
        public ArrayList<Integer> path;
        public ResultType(int sum, ArrayList<Integer> path){
            this.sum = sum;
            this.path = path;
        }
    }

    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        /**这道题用遍历会简单点，但是为了更好地理解分治，用分治实现
         * 分治的target是target减去root.val
         * 遍历出所有解后，去掉结果不等于target的解*/
         //result用于存储最终答案，paths用来保存目前的路径
        List<List<Integer>> result = new ArrayList<>();
        ArrayList<ResultType> paths = new ArrayList<>();
        //定义异常情况
        if(root == null){
            return result;
        }
        //用helper函数得到所有的paths
        paths = helper(root, target);
        //将paths中的每个path取出来暂存在temp中，然后加进result
        for(ResultType eachpath:paths){
            ArrayList<Integer> temp = eachpath.path;
            result.add(temp);
        }

        return result;
    }

    private ArrayList<ResultType> helper(TreeNode root, int target){

        ArrayList<ResultType> paths = new ArrayList<ResultType>();

        if (root == null) {
            return paths;
        }
        //处理左右子树为空的情况
        if(root.left == null && root.right == null){
            if(root.val == target) {
                ArrayList<Integer> temppath = new ArrayList<Integer>();
                temppath.add(root.val);
                ResultType temp = new ResultType(root.val, temppath);
                paths.add(temp);
            }
            return paths;
        }
        //两个小弟分别遍历左右子树
        ArrayList<ResultType> leftpaths = helper(root.left, target - root.val);
        ArrayList<ResultType> rightpaths = helper(root.right, target - root.val);
        //这里我本来用for( String path : leftpaths)，但是错了，因为必须有i
        //注意leftpaths是所有的解，需要从中找出等于target的解
        //这里用leftpaths.get(i)得到依次从左子树走下去的所有解
        //只要sum等于target，就把这个解加到paths里面
        int leftsize = leftpaths.size();
        for(int i = 0; i < leftsize; i++){
            ResultType leftpath = leftpaths.get(i);
            if(leftpath.sum == target - root.val){
                leftpath.sum = target;
                leftpath.path.add(0, root.val);
                paths.add(leftpath);
            }
        }

        int rightsize = rightpaths.size();
        for(int i = 0; i < rightsize; i++){
            ResultType rightpath = rightpaths.get(i);
            if(rightpath.sum == target - root.val){
                rightpath.sum = target;
                rightpath.path.add(0, root.val);
                paths.add(rightpath);
            }
        }

        return paths;
    }
}


traverse的解法
/**
 * 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
     */
    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        // Write your code here
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> paths = new ArrayList<>();
        if(root == null){
            return result;
        }
        paths.add(root.val);
        helper(result, paths, root, target,root.val);
        return result;
    }
    private void helper(List<List<Integer>> result,
                                        List<Integer> paths,
                                       TreeNode root, int target, int sum){

        if(root.left == null && root.right == null && sum ==target){
            result.add(new ArrayList<Integer> (paths));
            return;
        }
        if(root.left != null){
            paths.add(root.left.val);
            helper(result,paths,root.left,target, sum + root.left.val);
            paths.remove(paths.size()-1);
        }
        if(root.right != null){
            paths.add(root.right.val);
            helper(result,paths,root.right,target, sum + root.right.val);
            paths.remove(paths.size()-1);
        }
        
    }
}