题解 | #二叉树中和为某一值的路径(二)#

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

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

    }

}
*/
// 难点在于要维护一个全局数组，不好递归
// 且在单条路径递归的时候，要维护一组局部的历史节点
// 时间复杂度O（n^2）,空间复杂度O（n）
public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        // 终止条件1：节点为空，返回空数组
        if (root == null)
            return list;
        // 终止条件2：找到路径，返回此单值数组
        if (root.left == null && root.right == null && root.val == expectNumber){
            ArrayList<Integer> in_list = new ArrayList<>();
            in_list.add(expectNumber);
            list.add(in_list);
            return list;
        }
        // 把expectNumber值调整后向下传递
        ArrayList<ArrayList<Integer>> left = FindPath(root.left, expectNumber-root.val);
        ArrayList<ArrayList<Integer>> right = FindPath(root.right, expectNumber-root.val);
        // 把本级节点值加入后，合并左右返回数组，向上传递数组
        if (!left.isEmpty()){
            for(ArrayList<Integer> list1 : left){
                list1.add(0, root.val);
            }
        }
        if (!right.isEmpty()){
            for(ArrayList<Integer> list2 : right){
                list2.add(0, root.val);
            }
        }
        left.addAll(right);
        return left;
    }
}