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

import java.util.ArrayList;
import java.util.Stack;

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/


public class Solution {
    private ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
    private Stack<Integer>path = new Stack<>();//栈 
    
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        //遍历 所有可能的点都存到list中 最后走一遍
        if(root==null) return paths;
        path.push(root.val);
        expectNumber -= root.val;
        
        if(expectNumber==0 && root.right==null && root.left==null){
            paths.add(new ArrayList<Integer>(path));
        }
        FindPath(root.left,expectNumber);
        FindPath(root.right,expectNumber);
        path.pop();//深搜后回溯
        return paths;
    }
}

ArrayList中有一个 构造，可以传入 Collection接口的实现类。

因此直接用stack记录点，此后直接生成ArrayList

思路：dfs遍历，注意回溯

path.pop();：深搜后回溯