LeetCode 437. 路径总和 III题目理解给定一棵二叉树和一个整数 targetSum求路径和等于 targetSum 的路径数目。路径要求· 方向必须向下从父节点到子节点· 起点不一定是根节点终点不一定是叶子节点· 路径至少包含一个节点解法一前缀和 DFS推荐O(n)思路类似「数组中和为 targetSum 的子数组个数」把根到当前节点的路径看作一个数组。· 用 prefix 记录从根到当前节点的路径和· 用 HashMap 记录路径上出现过的前缀和及其出现次数· 若 prefix - targetSum 在 map 中出现过 k 次说明有 k 条以当前节点结尾、和为 targetSum 的路径关键点· map 初始放入 {0: 1}代表空前缀处理从根节点开始的情况· 回溯时要把当前前缀和的计数减掉保证 map 里只包含当前路径上的节点代码importjava.util.HashMap;importjava.util.Map;classSolution{publicintpathSum(TreeNoderoot,inttargetSum){// key: 前缀和, value: 该前缀和出现的次数MapLong,IntegerprefixMapnewHashMap();prefixMap.put(0L,1);// 空前缀处理从根开始的路径returndfs(root,0L,targetSum,prefixMap);}privateintdfs(TreeNodenode,longcurSum,inttargetSum,MapLong,IntegerprefixMap){if(nodenull)return0;curSumnode.val;// 以当前节点结尾的路径数curSum - targetSum 出现过几次intcountprefixMap.getOrDefault(curSum-targetSum,0);// 把当前前缀和加入 mapprefixMap.put(curSum,prefixMap.getOrDefault(curSum,0)1);// 递归左右子树countdfs(node.left,curSum,targetSum,prefixMap);countdfs(node.right,curSum,targetSum,prefixMap);// 回溯移除当前前缀和避免影响兄弟子树prefixMap.put(curSum,prefixMap.get(curSum)-1);returncount;}}复杂度· 时间O(n)每个节点访问一次· 空间O(h)h 为树高递归栈 map注意用 long 存前缀和防止节点值较大时溢出。解法二双重递归暴力O(n²)思路对每个节点都尝试把它作为路径起点向下搜索所有路径。代码classSolution{publicintpathSum(TreeNoderoot,inttargetSum){if(rootnull)return0;// 以 root 为起点 以左孩子为起点 以右孩子为起点returncountFrom(root,(long)targetSum)pathSum(root.left,targetSum)pathSum(root.right,targetSum);}// 从 node 出发向下路径和等于 target 的路径数privateintcountFrom(TreeNodenode,longtarget){if(nodenull)return0;intcount(node.valtarget)?1:0;countcountFrom(node.left,target-node.val);countcountFrom(node.right,target-node.val);returncount;}}复杂度· 时间O(n²)最坏情况树退化成链时· 空间O(h)对比解法 时间复杂度 空间复杂度 适用场景前缀和 DFS O(n) O(h) 推荐通用最优双重递归 O(n²) O(h) 思路简单数据量小时可用易错点提醒前缀和用 long节点值可能让和超过 int 范围prefixMap.put(0L, 1) 不要漏否则从根开始的路径会被漏掉回溯必须撤销否则会把其它分支的前缀和带进来导致错误路径方向是向下所以是 DFS 不是任意方向的路径