)
本题采用双重深度优先搜索递归算法（又称“嵌套双 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 | 状态判定与计数触发 | 空间调用栈物理状态说明 |
| 初始 | 5 | 5 | 8 | 5 不等于 8，计数暂为 0；触发子代探测 | 栈深: [pathSum(5), dfs(5,8)] |
| 1 | 5 | 3 | 8 - 5 = 3 | 3 == 3，触发命中，count自增 1；其左右孩子为空返回 0 | 栈深: [... -> dfs(3,3)] -> 弹出 |
| 2 | 5 | 2 | 8 - 5 = 3 | 2 不等于 3，返回 0；其左右孩子为空返回 0 | 栈深: [... -> dfs(2,3)] -> 弹出 |
| 3 | 5 | - | - | 内层dfs(5,8)归纳完成，返回 1 | 栈深: [pathSum(5)]，累加计数 = 1 |
| 4 | 5 (推进起点) | 3 | 8 | 外层调用pathSum(3)，内层dfs(3,8)启动 | 栈深: [pathSum(5), pathSum(3), dfs(3,8)] |
| 5 | 5 | 3 | 8 | 3 不等于 8，返回 0；左右子树为空返回 0 | 栈深: [... -> dfs(3,8)] -> 弹出 |
| 6 | 5 (推进起点) | 2 | 8 | 外层调用pathSum(2)，内层dfs(2,8)启动 | 栈深: [pathSum(5), pathSum(2), dfs(2,8)] |
| 7 | 5 | 2 | 8 | 2 不等于 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)。
