LeetCode437. 路径总和 III

给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。 示例1: 示例1

输入:root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出:3
解释:和等于 8 的路径有 3 条,如图所示。

前缀和

/**
     * 前缀和
     */
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> map = new HashMap<>();
//        当 targetSum 等于某个前缀和时,currPrefix - target = 0,当前节点自己就算做一条符合条件的路径,所以也要计数
        map.put(0L, 1);
        return preorder(root, map, targetSum, 0);
    }

    private int preorder(TreeNode node, Map<Long, Integer> map, int target, long currPrefix) {
        if (node == null) {
            return 0;
        }
        int num = 0;
//        当前前缀和
        currPrefix += node.val;
//        假设当前从根节点 root 到节点 node 的前缀和为 currPrefix
//        则在已保存的 前缀和 中查找是否存在 前缀和 刚好等于 currPrefix − target
//        假设从根节点 root 到节点 node 的路径中存在节点 P(i),到根节点 root 的前缀和为 currPrefix − target
//        则节点 P(i+1) 到 node 的路径上所有节点的和一定为 target
//                1
//               /
//              2
//             /
//            3
//           /
//          4
//        给定值为 target = 5
//        prefix(3) = 1 + 2 + 3 = 6
//        prefix(1) = 1
//        假设 currPrefix = prefix(3) = 6 即 node = 3
//        currPrefix - target = 1 = prefix(1) 即 P(1) , 已经在 map 中,value = 1
//        因此 num = 1 , P(1 + 1) = P(2) 到 P(3) 的路径和为 target = 5
        num += map.getOrDefault(currPrefix - target, 0);
//        当前前缀和数量 + 1
        map.put(currPrefix, map.getOrDefault(currPrefix, 0) + 1);
        num += preorder(node.left, map, target, currPrefix);
        num += preorder(node.right, map, target, currPrefix);
//        回溯,防止左边前缀树影响右边前缀树,因为当前节点的前缀和只对子节点有效
//        当前节点可能为父节点的左子节点,切换到父节点的右子节点后左子节点的数据不应当被采用
        map.put(currPrefix, map.getOrDefault(currPrefix, 0) - 1);
        return num;
    }

双递归DFS(超时)

/**
     * 一个朴素的做法是搜索以 每个节点 为根的(往下的)所有路径,并对路径总和为 targetSum 的路径进行累加统计
     * 在 pathSum2 中搜索所有节点,复杂度为 O(n)
     * 在 pathSum2 中对当前节点,使用 dfs 搜索以其为根的所有(往下的)路径,同时累加路径总和为 targetSum 的所有路径,复杂度为 O(n)
     */
    public int pathSum2(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
//        对当前节点深搜,获取符合条件的路径和
        var num = dfs(root, targetSum);
//        搜索所有节点,累加路径和
        num += pathSum2(root.left, targetSum);
        num += pathSum2(root.right, targetSum);
        return num;
    }

    private int dfs(TreeNode node, long targetSum) {
        if (node == null) {
            return 0;
        }
        int num = 0;
        if (node.val == targetSum) {
            num++;
        }
        num += dfs(node.left, targetSum - node.val);
        num += dfs(node.right, targetSum - node.val);
        return num;
    }

题目: 题目链接 参考题解: 官方解答 对前缀和解法的一点解释 【宫水三叶】一题双解 :「DFS」&「前缀和」

ねぇ,あなたは何色になりたい