437. 路径总和 III

题目链接：https://leetcode.cn/problems/path-sum-iii/

代码

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function pathSum(root: TreeNode | null, targetSum: number): number {
    let res = 0;
    function dfs(node: TreeNode | null): void {
        if (!node) return;
        sum(node, targetSum);
        dfs(node.left);
        dfs(node.right);
    }
    function sum(node: TreeNode | null, target: number): void {
        if (!node) return;
        target -= node.val;
        if(target === 0) res++;
        sum(node.left, target);
        sum(node.right, target);
    }
    dfs(root);
    return res;
};

思路

这份实现采用双层 DFS：

第一层 dfs 枚举每个节点，尝试把它作为路径起点
第二层 sum 从当前起点向下搜索，统计和为 targetSum 的路径数量

具体过程如下：

遍历整棵树中的每个节点
对于每个节点，调用 sum(node, targetSum)，统计从该节点出发的合法路径数
在 sum 中，每访问一个节点就让 target 减去当前节点值
如果 target === 0，说明当前路径和恰好等于目标值，答案加一
继续向左右子树递归，保持路径必须是向下延伸

关键点

路径不要求从根节点开始，但必须沿父子方向向下
dfs 负责“枚举起点”，sum 负责“统计从该起点出发的合法路径”
同一条路径中的节点必须连续，不能跳跃
该实现思路直观，适合理解题意
时间复杂度： $O (n^{2})$ ，最坏情况下每个节点都要向下搜索一遍
空间复杂度： $O (h)$ ，其中 $h$ 是树的高度，主要为递归栈开销

437. 路径总和 III ​

代码 ​

思路 ​

关键点 ​

437. 路径总和 III

代码

思路

关键点