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

import java.util.*;

public class Solution {
    // 存储目标路径
    private static ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    // 拼接当前路径
    private static LinkedList<Integer> path = new LinkedList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int targetSum) {
        // 预处理
        if (root == null) return res;
        // 使用深度优先搜索查找整棵树
        dfs(root, targetSum);
        // 返回结果集
        return res;
    }

    // 深度优先搜索查找目标路径
    public static void dfs(TreeNode root, int targetSum) {
        // 预处理
        if (root == null) return;
        // 更新当前路径和目标值
        path.add(root.val);
        targetSum -= root.val;
        // 如果当前结点为叶子结点且已经达到了目标和
        if (isLeaf(root) && targetSum == 0) {
            // 记录当前路径
            res.add(new ArrayList<>(path));
        }
        // 递归查找其左右子树
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
        // 回溯
        path.removeLast();
    }

    // 判断当前结点是否为叶子结点
    public static boolean isLeaf(TreeNode node) {
        // 预处理
        if (node == null) return false;
        // 当前结点没有左右结点即为叶子结点
        return node.left == null && node.right == null;
    }
}