【NC8】二叉树根节点到叶子节点和为指定值的路径

题目链接：https://www.nowcoder.com/practice/840dd2dc4fbd4b2199cd48f2dadf930a?tpId=188&&tqId=36537&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking

思路：首先如果想要知道根节点到叶子结点和为指定值的所有路径，那么我们就需要遍历根节点到叶子结点的所有路径，那么我们递归遍历每一个结点，在这个过程中同时记录之前经过的所有节点即可。

实现：在递归的同时记录已经走过的节点，方法中传入的值是放在堆空间中，还是放在栈空间中，是共享的，还是每一个结点独自占有的。这里给出两种方法：

• 使用一个临时变量记录当前走过的路径和，等到达叶子结点的时候判断当前路径和为sum；
• 有兴趣可以自己画一下在递归的时候内存变化情况。

import java.util.*;
public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        // write code here
        ArrayList<Integer> res = new ArrayList<>(); // 这里可以定义为成员变量
        ArrayList<ArrayList<Integer> > list = new ArrayList<>();
        dfs(root, 0, sum, res, list);
        return list;
    }
    public void dfs(TreeNode root, int cur, int sum, ArrayList<Integer> res, ArrayList<ArrayList<Integer> > list) {
        if (root == null) return ;
        res.add(root.val);
        cur += root.val;
        if (cur == sum && root.left == null && root.right == null) {
            list.add(res);
            return ;
        }
        // 这里需要注意新添加一个ArrayList集合，list指向的是res的地址。
        dfs(root.left, cur, sum, new ArrayList<>(res), list);
        dfs(root.right, cur, sum, new ArrayList<>(res), list);
        res.remove(res.size() - 1);
    }
}

import java.util.*;
public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        // write code here
        ArrayList<Integer> res = new ArrayList<>();
        ArrayList<ArrayList<Integer> > list = new ArrayList<>();
        dfs(root, sum, res, list);
        return list;
    }
    public void dfs(TreeNode root, int sum, ArrayList<Integer> res, ArrayList<ArrayList<Integer> > list) {
        if (root == null) return ;
        res.add(root.val);
        sum -= root.val;
        if (root.left == null && root.right == null && sum == 0) {
            list.add(res);
            return ;
        }
        // 这里需要注意新添加一个ArrayList集合，list指向的是res的地址。
        dfs(root.left, sum, new ArrayList<>(res), list);
        dfs(root.right, sum, new ArrayList<>(res), list);
        res.remove(res.size() - 1);
    }
}