力扣---剑指 Offer 34. 二叉树中和为某一值的路径

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
示例 2：

输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：

输入：root = [1,2], targetSum = 0
输出：[]
 

提示：

树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

深度优先搜索，大致思路是用一个 list 来存储路径信息，用一个 sum 来存储路径值的和。遇到 target 和 sum 相等的情况时，判断该节点是不是叶节点（左节点和右节点都为 null）。

剩下的看注释：

class Solution {
    public List<List<Integer>> pathSum (TreeNode root, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        // 深度优先搜索。
        dfs(root, target, res, new ArrayList<Integer>(), 0);
        return res;
    }
    // root：当前节点。  target：需要等于的值。  res：最后返回的答案。  list：从根结点到当前节点的路径。  sum：从根结点到当前节点的路径值的和。
    private void dfs (TreeNode root, int target, List<List<Integer>> res, List<Integer> list, int sum) {
        // 当前节点为 null 时直接返回。
        if (root == null) {
            return;
        }
        // 更新路径和节点和。
        list.add(root.val);
        sum += root.val;
        // 由于包含负数，所以只能用 == 来判断。
        if (sum == target) {
            // 需要子节点全为null。
            // 由于存在之后子节点的值和为 0 的情况，所以不能直接返回，还需要对子节点进行判断。
            if (root.left == null && root.right == null) {
                // 因为 ArrayList 是引用数据，所以不能直接添加，而应该加入复制。
                res.add(new ArrayList<Integer>(list));
                // 还原操作。
                list.remove(list.size() - 1);
                return;
            }
        }
        // 左节点
        dfs(root.left, target, res, list, sum);
        // 右节点
        dfs(root.right, target, res, list, sum);
        // 还原操作。
        list.remove(list.size() - 1);
    }
}