知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 11 - 路径总和 III ## 题目(LeetCode 437) 给定一棵二叉树和一个目标值 targetSum,找出路径和等于 targetSum 的路径数量。路径不需要从根节点开始,也不需要在叶子节点结束,但方向必须是向下的(从父到子)。 ``` 10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1 targetSum = 8 满足条件的路径有 3 条: 5 → 3 = 8 5 → 2 → 1 = 8 -3 → 11 = 8 ``` ## 大白话理解 ### 暴力思路(容易理解但慢) 对每个节点,都把它当作起点,往下找所有路径,看有没有和为 targetSum 的。 ``` 以 10 为起点:10, 10→5, 10→5→3, 10→5→3→3, ... 以 5 为起点:5, 5→3, 5→3→3, 5→3→-2, 5→2, 5→2→1 以 -3 为起点:-3, -3→11 ... ``` 时间复杂度 O(n²),能过但不够优雅。 ### 前缀和思路(O(n),重点) 这个技巧和"数组中和为 k 的子数组"一模一样。 核心思想:如果从根到当前节点的路径和为 `curSum`,而之前某个祖先节点处的路径和为 `curSum - targetSum`,那么从那个祖先到当前节点的路径和就是 `targetSum`。 ``` 路径:根 → ... → 祖先A → ... → 当前节点 |←── prefixSum ──→|←── targetSum ──→| |←────────── curSum ────────────────→| curSum - targetSum = prefixSum 如果 prefixSum 在之前出现过,说明存在一条路径和为 targetSum ``` 用 HashMap 记录"从根到当前路径上,每个前缀和出现了几次"。 ## 代码 ```java class Solution { public int pathSum(TreeNode root, int targetSum) { // key: 前缀和, value: 出现次数 Map<Long, Integer> prefixMap = new HashMap<>(); prefixMap.put(0L, 1); // 前缀和为 0 出现 1 次(空路径) return dfs(root, 0L, targetSum, prefixMap); } private int dfs(TreeNode node, long curSum, int target, Map<Long, Integer> prefixMap) { if (node == null) return 0; curSum += node.val; // 看看有没有前缀和 = curSum - target // 如果有,说明从那个位置到当前节点的路径和 = target int count = prefixMap.getOrDefault(curSum - target, 0); // 把当前前缀和加入 map prefixMap.merge(curSum, 1, Integer::sum); // 递归左右子树 count += dfs(node.left, curSum, target, prefixMap); count += dfs(node.right, curSum, target, prefixMap); // 回溯:离开当前节点时,把当前前缀和从 map 中移除 prefixMap.merge(curSum, -1, Integer::sum); return count; } } ``` ### 为什么要回溯? ``` 1 / \ 2 3 假设 target = 3 走左边:前缀和 1, 3(路径 1→2) 走右边:前缀和 1, 4(路径 1→3) 如果不回溯,走右边时 map 里还有左边的前缀和 3 可能会错误地认为"从前缀和 3 的位置到当前节点"是一条合法路径 但那个前缀和 3 是左子树的,不在当前路径上 所以离开一个节点时,必须把它的前缀和从 map 中移除 ``` ### 为什么初始化 `prefixMap.put(0, 1)`? 处理从根节点开始的路径。如果从根到当前节点的路径和恰好等于 target,那么 `curSum - target = 0`,需要在 map 中找到 0。 ## 画图模拟 ``` target = 8 10 / \ 5 -3 / \ \ 3 2 11 DFS 过程(只展示关键步骤): 节点 10: curSum=10, 查找 10-8=2 → 没有 → count=0 map: {0:1, 10:1} 节点 5: curSum=15, 查找 15-8=7 → 没有 → count=0 map: {0:1, 10:1, 15:1} 节点 3: curSum=18, 查找 18-8=10 → 有!count=1(路径 5→3) map: {0:1, 10:1, 15:1, 18:1} 节点 2: curSum=17, 查找 17-8=9 → 没有 → count=0 map: {0:1, 10:1, 15:1, 17:1} 节点 1: curSum=18, 查找 18-8=10 → 有!count=1(路径 5→2→1) map: {0:1, 10:1, 15:1, 17:1, 18:1} 节点 -3: curSum=7, 查找 7-8=-1 → 没有 节点 11: curSum=18, 查找 18-8=10 → 有!count=1(路径 -3→11) 总计:3 条路径 ✓ ``` ## 复杂度 - 时间:O(n),每个节点访问一次 - 空间:O(h),递归栈 + HashMap ## 一句话总结 前缀和 + HashMap + DFS 回溯。`curSum - target` 在 map 中出现几次,就有几条路径。别忘了回溯。 --- 上一篇:[10 - 二叉树的序列化与反序列化](./10-serialize.md) | 下一篇:[12 - 二叉树中的最大路径和](./12-max-path-sum.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入