47. 二叉树中和为某一值的路径

输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。

算法1

(递归)

Java 代码

class Solution {
    List <List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> findPath(TreeNode root, int sum) {
        dfs(root, sum, new ArrayList<>());

        return res;
    }

    private void dfs(TreeNode root, int sum, ArrayList<Integer> path){
        if(root == null) return;
        sum -= root.val;

        path.add(root.val);
        if(root.right == null && root.left == null && sum == 0)
            res.add(new ArrayList<>(path));//引用调用，需要新建path内容，不然存在res中的为引用，在后面remove之后即为空
        dfs(root.left, sum, path);
        dfs(root.right, sum, path);
        path.remove(path.size()-1);
    }
}