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

O(N),穷举

在递归过程中，递归终止条件很重要，因为只有叶子节点的时候，才可以返回 return；

此代码中，每次减去遍历过的数值expectNumber - root.val，但是切记要回溯

import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> res;
LinkedList<Integer> path;
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
    res = new ArrayList<>();
    path = new LinkedList<>();
    tracking(root, expectNumber);
    return res;
}

public void tracking(TreeNode root, int expectNumber){
    if(root == null) return;
    
    if(root.left == null && root.right == null){//叶子节点
        if(expectNumber == root.val){
            path.add(root.val);
            res.add(new ArrayList<>(path));
            path.poll();
        }
        return;
    }
    
    path.add(root.val);
    tracking(root.left, expectNumber - root.val);
    path.pollLast();//回溯
    
    path.add(root.val);
    tracking(root.right, expectNumber - root.val);
    path.pollLast();//回溯
    
}
}