.jpg)
584 字
3 分钟
路径总和 III
题目描述
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
解题思路
- 双重DFS：
- 外层DFS遍历所有节点作为路径起点
- 内层DFS计算以当前节点为起点的路径和
- 前缀和优化：
- 哈希表记录路径前缀和出现次数
- 当前前缀和 - targetSum 查表获得有效路径数
- 回溯维护：递归时更新哈希表，回溯时恢复状态
- 边界处理：初始化哈希表
{0:1}处理根节点自身满足条件的情况
关键洞察
- 子问题分解：任意节点都可作为路径起点或中间点
- 前缀和原理：
当前和 - targetSum = 历史前缀和即存在有效路径 - 哈希表加速：将O(n²)暴力搜索优化为O(n)查询
- 回溯必要性：确保哈希表仅记录当前路径的前缀和
- 空路径初始化：
{0:1}处理路径正好等于targetSum的情况
复杂度分析
- 时间复杂度：
- 暴力DFS：O(n²)
- 前缀和+DFS：O(n)
- 空间复杂度：O(n)
- 递归栈O(h) + 哈希表O(n)（h为树高）
代码实现
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @param {number} targetSum * @return {number} */var pathSum = function (root, targetSum) { if (!root) return 0; // 初始化前缀和映射表（前缀和 -> 出现次数） const prefixSum = new Map(); prefixSum.set(0, 1); // 关键：空路径前缀和为0 let count = 0; const dfs = (node, currentSum) => { if (!node) return; // 计算当前节点前缀和 currentSum += node.val; // 检查是否存在有效路径：当前和 - targetSum = 历史前缀和 const prevSum = currentSum - targetSum; count += prefixSum.get(prevSum) || 0; // 更新当前前缀和的计数 prefixSum.set(currentSum, (prefixSum.get(currentSum) || 0) + 1); // 递归遍历子树 dfs(node.left, currentSum); dfs(node.right, currentSum); // 回溯：移除当前节点贡献的前缀和 prefixSum.set(currentSum, prefixSum.get(currentSum) - 1); }; dfs(root, 0); return count;};