本题采用双重深度优先搜索递归算法又称“嵌套双 DFS 遍历法”解决非固定起点与终点的二叉树向下路径和计数问题。其核心本质是以外部递归遍历全树所有节点作为路径起点叠加内部递归自顶向下追踪递减后的剩余目标和的匹配状态并通过长整型类型转换消除大数值累加引发的溢出干扰。当前提供的源码实现了在最坏时间复杂度 O(n^2) 和额外空间复杂度 O(h)其中 h 为树的高度条件下的全局路径枚举最终走向是精准返回满足目标和的全部向下路径总数。一、 问题本质与数据模型对于给定的二叉树与目标和 targetSum路径的拓扑结构模型具备高度的开放性拓扑开放性约束路径不需要从根节点开始也不需要在叶子节点结束这打破了常规二叉树路径问题固有的边界限制。单向流动约束路径方向必须严格向下只能从父节点流向子节点保留了树状结构的层次单调性。由于路径的起点可以在全树的任意节点触发这就要求算法具备全局起点的扫描能力。在无先验前缀和缓存的前提下必须将二叉树中的每一个物理节点都虚拟视作潜在的路径始发站。同时题目提示中节点值范围达到了 -10^9 到 10^9 阶。在路径自顶向下推进的过程中连续扣减或累加操作极易突破标准 32 位整型int的数值边界从而引发隐蔽的整型溢出错误。算法引入了(long) targetSum的拓扑空间扩展在数据模型层面保证了全路径比对的边界安全性。二、 算法演进对比在解决不固定起终点的二叉树路径和问题时嵌套双 DFS 法表现出逻辑清晰、空间占用受控的特征解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷前缀和哈希表回溯法O(n)O(h)借助回溯维护根节点到当前节点的前缀和通过哈希表在 O(1) 内锁定目标差值频率需要维护外部哈希表状态回溯时的清理逻辑较复杂内存开销随深度递增双重 DFS 暴力枚举当前解法O(n^2)O(h)嵌套两层递归外层控制路径起点的推进内层负责向后代探测扣减后的剩余目标值存在大量重复的节点重复访问与状态测算在倾斜树拓扑下性能大幅退化拓扑图转化法O(n)O(n)将二叉树转换为无向图利用广度优先搜索进行全路径探测完全破坏了二叉树固有的单向层次特征且带来了极大的空间结构开销三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于外层起点调度函数pathSum与内层路径追踪函数dfs的嵌套协作其内部决策分支证明如下1. 外层基准退出与组合分支if (root null)执行返回 0非空时返回dfs(root, ...)与左右子树pathSum的线性加和。数学证明外层递归负责穷举全树所有可能的起点。空节点无法作为路径起点高度贡献为 0。对于非空节点以其为起点的全局路径总数必然等于以当前 root 为起点的路径数加上在其左子树中任意节点为起点的路径数以及在其右子树中任意节点为起点的路径数。三者在空间上互不重叠满足加法原理。2. 内层基准退出分支if (root null)执行直接返回 0。物理意义内层探测触及虚拟空边界说明当前向下搜索的弹道已中断无法继续向后代延伸或提供数值扣减返回计数 0。3. 局部目标命中分支if (root.val target)执行count;但不终止流程继续向下执行。数学证明当前节点的值精确等于当前被扣减后的期望目标值。这证明从内层递归的起始节点到当前节点的这条路径是一条合法路径计数器自增 1。由于树节点中可能存在 0 或负数后续路径继续向下累加仍有可能再次使路径和等于目标值例如路径序列 [5, 2, -2] 的前缀和在 5 和 -2 处可能多次触发命中因此命中后不能中断必须继续向深层探测。4. 内层状态向下传递执行count dfs(root.left, target - root.val);和count dfs(root.right, target - root.val);数学证明当前节点已被纳入路径后续节点需要匹配的剩余目标值变更为target - root.val。通过将此状态分别传递给左右子树完成深层后代路径的全局扫描与计数归纳。四、 算法执行状态机步进示例以输入二叉树root [5, 3, 2]目标值targetSum 8为例其中 5 为根3 为左孩子2 为右孩子嵌套状态机的演进过程如下表所示步骤外层激活节点 (起点)内层探测节点传入内层的当前 target状态判定与计数触发空间调用栈物理状态说明初始5585 不等于 8计数暂为 0触发子代探测栈深: [pathSum(5), dfs(5,8)]1538 - 5 33 3触发命中count自增 1其左右孩子为空返回 0栈深: [... - dfs(3,3)] - 弹出2528 - 5 32 不等于 3返回 0其左右孩子为空返回 0栈深: [... - dfs(2,3)] - 弹出35--内层dfs(5,8)归纳完成返回 1栈深: [pathSum(5)]累加计数 145 (推进起点)38外层调用pathSum(3)内层dfs(3,8)启动栈深: [pathSum(5), pathSum(3), dfs(3,8)]55383 不等于 8返回 0左右子树为空返回 0栈深: [... - dfs(3,8)] - 弹出65 (推进起点)28外层调用pathSum(2)内层dfs(2,8)启动栈深: [pathSum(5), pathSum(2), dfs(2,8)]75282 不等于 8返回 0左右子树为空返回 0栈深: [... - dfs(2,8)] - 弹出8---全局外层加和1 0 0 1流程结束最终输出 1调用栈完全清空五、 源码实现/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public int pathSum(TreeNode root, int targetSum) { // 基准收敛条件若当前节点为空说明无法作为路径起点返回 0 if (root null) { return 0; } // 核心控制全局路径总数 以当前 root 为起点的路径数 以左子树各节点为起点的路径数 以右子树各节点为起点的路径数 // 将 targetSum 强转为 long 类型向下传递防止后续连续减法引发的整型溢出 return dfs(root, (long) targetSum) pathSum(root.left, targetSum) pathSum(root.right, targetSum); } private int dfs(TreeNode root, long target) { // 基准收敛条件触及空节点边界路径中断返回计数 0 if (root null) { return 0; } int count 0; // 分支判定若当前节点值精确匹配剩余目标值则找到一条合法向下路径 if (root.val target) { count; } // 状态传递包含当前节点后继续向左、右子树探测剩余的目标和值并累加计数结果 count dfs(root.left, target - root.val); count dfs(root.right, target - root.val); // 状态回溯返回当前局部弹道内累加出来的所有合法路径总数 return count; } }六、 复杂度分析1. 时间复杂度O(n^2)分析算法包含两层相互嵌套的递归。外层递归pathSum会对二叉树中的每一个节点进行一次访问总共执行 n 次。对于外层访问的每一个节点都会将其作为起点触发一次内层递归dfs。在最坏情况下二叉树拓扑结构极度倾斜退化为单链表结构第 1 个节点需要向下探测 n 个节点第 2 个节点需要探测 n-1 个节点依此类推整体基本比较操作构成等差数列n (n-1) ... 1。结论最坏时间复杂度定性为 O(n^2)在高度完全平衡的二叉树结构下各层节点单调对半分切内层平均探测深度被控制在对数阶总时间复杂度可以优化收敛至 O(n log n)。2. 空间复杂度O(h)分析算法在执行全流程中除局部变量计数器外并未显式申请任何与输入规模成正比的堆内存独立数据结构。空间的动态消耗完全由系统方法调用栈的物理深度决定。外层方法栈与内层方法栈在最深推进路径上是并行存在的其最大累加深度等于二叉树的物理高度 h。结论空间复杂度表示为 O(h)。在最坏单链表树下空间复杂度为 O(n)在平衡二叉树的最佳拓扑下空间复杂度降为 O(log n)。