【小白也能懂】二叉树中和为某一值的路径

题目描述
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

1. 首先我们可以发现，我们需要遍历整个二叉树，所以我们需要一个辅助function来帮助我们遍历每个节点。在此时我们可以运用DFS
2. 然后，我们需要注意的是，我们同时需要一个Arraylist帮助我们储存我们来到遍历的当前节点之前的路径
3. 接着，我们需要一个Arraylist<ArrayList<integer>>来作为我们最后需要返回的结果，来储存所有2里符合条件的Arraylist</integer>

这题有一个重点，就是 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径， 所以我们要确保最后一个加进去Arraylist的节点为叶节点，即确保当前遍历的节点无左孩子也无右孩子。

完整java解析如下：

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if(target == 0 || root == null){
            return result;
        }

        recur(root,target,new ArrayList<Integer>(),0,result);
        return result;
    }

    public void recur(TreeNode root,int target, ArrayList<Integer> temp,int cur, 
                      ArrayList<ArrayList<Integer>> result){
        if(root == null || cur + root.val > target){
            return;
        }
        if(root.left == null && root.right == null){
            if(root.val + cur == target){
            temp.add(root.val);
            result.add(temp);
            return;
            }
        }

        temp.add(root.val);
        if(root.left != null){
            recur(root.left,target,(ArrayList<Integer>)temp.clone(),cur+root.val,result);
        }
        if(root.right != null){
            recur(root.right,target,(ArrayList<Integer>)temp.clone(),cur+root.val,result);
        }
    }
}