Hot 100 --- 路径总和 III

本文概览本文以LeetCode题目路径总和III为例讲解二叉树上的前缀和哈希表方法重点说明与数组版560题的区别——多路径导致需要回溯哈希表一、题目二、题目分析题目要求给定二叉树的根节点和一个整数targetSum求节点值之和等于targetSum的路径数目。路径不需要从根节点开始也不需要在叶子节点结束但必须从父节点到子节点往下走这道题和力扣 560 题和为 K 的子数组是同一个思路——前缀和 哈希表。但二叉树比数组多了一个核心问题路径有分支。数组是一条路走到底而二叉树遍历完左子树要换到右子树这个换路的过程就是回溯哈希表必须跟着回溯否则右子树会查到左子树的残留数据我之前也发布了560题的题解,有需要的可以去看一下 : 和为k的子数组思路概览Java 实现代码如下publicintpathSum(TreeNoderoot,inttargetSum){MapLong,IntegermapnewHashMap();// 初始化map.put(0L,1);returndfs(root,0L,map,targetSum);}privateintdfs(TreeNodenode,longcurSum,MapLong,Integermap,longtargetSum){// 递归出口if(nodenull){return0;}// 当前节点的路径和curSumnode.val;// 查找符合条件的路径数量intcountmap.getOrDefault(curSum-targetSum,0);// 添加当前节点的路径和map.put(curSum,map.getOrDefault(curSum,0)1);// 递归搜索左子树countdfs(node.left,curSum,map,targetSum);countdfs(node.right,curSum,map,targetSum);// 回溯map.put(curSum,map.get(curSum)-1);returncount;}思路简要说明整体思路分三层前缀和算出每个节点从根到自身的路径和curSum。如果当前curSum减去之前某个节点的前缀和等于targetSum说明这两个节点之间的路径和就是targetSum哈希表加速用哈希表记录遍历过的前缀和及出现次数每到一个节点查curSum - targetSum在不在表里O(1) 完成查找回溯二叉树有分支遍历完一个节点的子树后要把它的前缀和从哈希表中删掉计数 -1这样回到上层去走另一条分支时哈希表里只保留当前路径上的前缀和另外两个细节哈希表 key 用Long防溢出初始放入(0L, 1)处理从根节点开始就满足条件的情况三、思路详解第一步前缀和的思路先回忆前缀和解决路径和等于目标值的核心思想假设从根到当前节点的路径和是curSum从根到之前某个祖先节点的路径和是preSum。如果curSum - preSum targetSum说明从那个祖先节点的下一个节点到当前节点的路径和恰好等于targetSum根 → ... → 祖先节点 → ... → 当前节点 preSum 根到祖先节点的和 curSum 根到当前节点的和 curSum - preSum 祖先节点之后到当前节点的和 如果 curSum - preSum targetSum就找到了一条符合条件的路径所以每到一个节点只需要查**之前有没有某个前缀和等于curSum - targetSum有几个**用哈希表记录前缀和出现的次数查找就是 O(1)第二步从一条路径到多条路径在数组560 题中路径只有一条从头到尾遍历一遍哈希表只管往里加不需要删但二叉树是一棵树从根往下走会有分叉。用 DFS 先序遍历时走到左子树最深处后要退回来走右子树。这个退回来就是问题所在看这棵树10 / \ 5 -3 / \ 3 2先序遍历的顺序是10 → 5 → 3 → 2 → -3遍历到 3 时curSum 181053哈希表里存了{0, 10, 15}遍历完 3 要去 2此时 3 这条路走完了3 的前缀和 18 必须清掉同样遍历完 5 的整个左子树3、2 都走完了要回到 10 去走右子树 -3 了5 子树中的所有前缀和15、18、17都必须清掉只要切换分支就必须清理。因为哈希表里存的是当前路径上经过的前缀和一旦离开这条路径这些前缀和就不再属于当前路径了。如果不清掉去 -3 那边查找时就会查到左子树残留的前缀和这些数据和右子树毫无关系会导致多算解决方法就是回溯遍历完一个节点的左右子树后把它的前缀和从哈希表中删掉计数 -1。这样回到上层去走另一条分支时哈希表里只有当前路径上的前缀和第三步为什么用先序遍历前缀和的核心是从根节点一直往下累加。只有先序遍历根→左→右才能保证每到一个节点时curSum就是从根节点到当前节点的路径和10 / \ 5 -3 先序遍历10 → 5 → -3 curSum 10 → 15 → 7 每一步都是从根到当前节点的路径和 ✓ 中序遍历5 → 10 → -3 curSum 5 → 15 → 12 第一步 5 不是从根到5的路径和应该是15前缀和意义失效 ✗第四步完整的执行过程以这棵树为例targetSum 810 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1满足条件的路径有三条5→3和8、5→2→1和8、-3→11和8下面逐步走一遍。核心要盯住哈希表的状态——它必须始终只反映当前正在走的那条路径上的前缀和。进入一个节点时把前缀和加进去离开这个节点时把前缀和拿出来哈希表就始终和当前路径同步初始状态哈希表{0:1}0 表示还没开始走的状态访问节点 10当前路径10curSum 0 10 10查 10 - 8 2 → 哈希表{0:1}中没有 2没找到把 10 加入哈希表 →{0:1, 10:1}继续往左子树 5 走访问节点 5当前路径10→5curSum 10 5 15查 15 - 8 7 → 哈希表{0:1, 10:1}中没有 7没找到把 15 加入哈希表 →{0:1, 10:1, 15:1}继续往左子树 3 走访问节点 3当前路径10→5→3curSum 15 3 18查 18 - 8 10 → 哈希表{0:1, 10:1, 15:1}中 10 出现 1 次找到一条路径这条路径是从前缀和为 10 的节点即根节点 10的下一个节点5到当前节点3也就是 5→3和为 8 ✓把 18 加入哈希表 →{0:1, 10:1, 15:1, 18:1}继续往左子树 3 走访问节点 3当前路径10→5→3→3curSum 18 3 21查 21 - 8 13 → 哈希表中没有 13没找到把 21 加入哈希表 →{0:1, 10:1, 15:1, 18:1, 21:1}左右子树为空此路走到底回溯把 21 从哈希表删掉 →{0:1, 10:1, 15:1, 18:1}访问节点 -2当前路径10→5→3→-2curSum 18 (-2) 16查 16 - 8 8 → 哈希表中没有 8没找到把 16 加入哈希表 →{0:1, 10:1, 15:1, 18:1, 16:1}左右子树为空回溯把 16 删掉 →{0:1, 10:1, 15:1, 18:1}节点 3 的左右子树都走完了回溯把 18 删掉 →{0:1, 10:1, 15:1}访问节点 2当前路径10→5→2curSum 15 2 17查 17 - 8 9 → 哈希表{0:1, 10:1, 15:1}中没有 9没找到把 17 加入哈希表 →{0:1, 10:1, 15:1, 17:1}继续往右子树 1 走访问节点 1当前路径10→5→2→1curSum 17 1 18查 18 - 8 10 → 哈希表中 10 出现 1 次找到一条路径从前缀和为 10 的节点根节点 10的下一个节点5到当前节点1也就是 5→2→1和为 8 ✓把 18 加入哈希表 →{0:1, 10:1, 15:1, 17:1, 18:1}左右子树为空回溯把 18 删掉 →{0:1, 10:1, 15:1, 17:1}节点 2 的子树走完回溯把 17 删掉 →{0:1, 10:1, 15:1}节点 5 的子树全部走完回溯把 15 删掉 →{0:1, 10:1}访问节点 -3当前路径10→-3curSum 10 (-3) 7查 7 - 8 -1 → 哈希表{0:1, 10:1}中没有 -1没找到把 7 加入哈希表 →{0:1, 10:1, 7:1}继续往右子树 11 走访问节点 11当前路径10→-3→11curSum 7 11 18查 18 - 8 10 → 哈希表{0:1, 10:1, 7:1}中 10 出现 1 次找到一条路径从前缀和为 10 的节点根节点 10的下一个节点-3到当前节点11也就是 -3→11和为 8 ✓把 18 加入哈希表 →{0:1, 10:1, 7:1, 18:1}左右子树为空回溯把 18 删掉 →{0:1, 10:1, 7:1}节点 -3 的子树走完回溯把 7 删掉 →{0:1, 10:1}节点 10 的子树全部走完回溯把 10 删掉 →{0:1}最终结果找到 3 条路径5→3 和为 8 ✓ 5→2→1 和为 8 ✓ -3→11 和为 8 ✓第五步哈希表的动态维护回头看整个过程哈希表的状态是动态变化的它始终只反映当前正在走的那条路径走到节点 10→5→3 时哈希表是{0, 10, 15, 18}这正是路径 10→5→3 上每个节点的前缀和当从 3 回退到 5 去走 2 时18 被删掉了哈希表变成{0, 10, 15}对应路径 10→5当从 5 回退到 10 去走 -3 时15 也被删掉了哈希表变成{0, 10}对应路径 10进入节点就加离开节点就删——这就是哈希表动态维护的规则。通过这个规则哈希表始终和当前路径同步查找时查到的永远是当前路径上的前缀和不会混入其他分支的数据这就是回溯的本质不是回到上一个状态而是把当前状态清理干净让下一次查找在正确的路径上进行第六步两个关键细节1. 为什么初始要放(0L, 1)考虑这种情况从根节点到某个节点的整条路径和恰好等于targetSum此时curSum - targetSum 0需要在哈希表中查到 0。但 0 不是任何节点的路径和它表示还没开始走的状态。如果不初始化(0, 1)这种情况就会漏掉比如上面例子中如果targetSum 18路径10→5→3的和恰好是 18。此时curSum 18查18 - 18 0哈希表中 0 出现 1 次count 加 1。这就是初始化的作用2. 为什么用 Long 不用 int节点值范围-10^9到10^9节点数最多 1000。前缀和最坏1000 × 10^9 10^12超出 int 范围约2×10^9必须用 Long和 560 题的对比560 题数组路径总和 III二叉树路径结构一条线性路径多条分支路径遍历方式从左到右一遍先序遍历DFS哈希表只加不删加完要删回溯前缀和含义从第0个到当前的累加从根到当前节点的累加核心区别不需要回溯必须回溯核心区别就是回溯。数组只有一条路哈希表只管加不管删。二叉树有分支遍历完左子树要退回来走右子树哈希表必须跟着退否则右子树会查到左子树的残留数据复杂度分析时间复杂度O(n)每个节点遍历一次哈希表查找 O(1)空间复杂度O(n)哈希表最多存 n 个前缀和递归栈 O(h)