lint0376. Binary Tree Path Sum

• 对应LeetCode 113. Path Sum II
  打印出所有从根到叶子的路径和等于target的路径
  Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target.

/**
 * 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 {
    private void helper(TreeNode root,ArrayList<Integer> path,
                        int sum,int target,List<List<Integer>> ret){
        if(root.left==null && root.right==null){
            if(sum == target)
                ret.add(new ArrayList<Integer>(path));
        }
        if(root.left!=null){
            path.add(root.left.val);
            helper(root.left,path,sum+root.left.val,target,ret);
            path.remove(path.size()-1);
        }
        if(root.right!=null){
            path.add(root.right.val);
            helper(root.right,path,sum+root.right.val,target,ret);
            path.remove(path.size()-1);
        }
    }
    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        // Algorithm: Preorder Traverse
        List<List<Integer>> ret = new ArrayList<>();
        if(root==null)
            return ret;
        ArrayList<Integer> path = new ArrayList<Integer>();
        path.add(root.val);
        helper(root, path, root.val, target, ret);
        return ret;
    }
}