LeetCode437. 路径总和 III

博主： Mashiro
发布时间：2023 年 01 月 17 日
376 次浏览
暂无评论
3311字数
分类：算法

# LeetCode437. 路径总和 III

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

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例1：
![示例1](https://assets.leetcode.com/uploads/2021/04/09/pathsum3-1-tree.jpg)

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

## 前缀和

```java
/**
     * 前缀和
     */
    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(超时)

```java
/**
     * 一个朴素的做法是搜索以 每个节点 为根的（往下的）所有路径，并对路径总和为 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;
    }
```

题目：
[题目链接](https://leetcode.cn/problems/path-sum-iii)
参考题解：
[官方解答](https://leetcode.cn/problems/path-sum-iii/solution/lu-jing-zong-he-iii-by-leetcode-solution-z9td/)
[对前缀和解法的一点解释](https://leetcode.cn/problems/path-sum-iii/solution/dui-qian-zhui-he-jie-fa-de-yi-dian-jie-s-dey6/)
[【宫水三叶】一题双解 :「DFS」&「前缀和」](https://leetcode.cn/problems/path-sum-iii/solution/gong-shui-san-xie-yi-ti-shuang-jie-dfs-q-usa7/)

最后修改：2023 年 01 月 17 日