112. 路径总和

112. 路径总和

题目描述

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum。

判断该树中是否存在 从根节点到叶子节点 的路径，这条路径上所有节点值相加等于 targetSum。

如果存在，返回 true；否则，返回 false。

说明

这里的 叶子节点 是指：

  • 没有左孩子
  • 也没有右孩子

的节点。

示例 1

text
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true

示例 2

text
输入：root = [1,2,3], targetSum = 5
输出：false

示例 3

text
输入：root = [], targetSum = 0
输出：false

约束

  • 树中节点的数目在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

核心思路

这题最容易看错的地方有两个：

  1. 必须是 从根到叶子 的完整路径
  2. 不是只要中途某个前缀和等于 targetSum 就算成功

所以本题本质上是在做：

  • 从根节点往下搜索每一条路径
  • 同时维护“当前还差多少和”或者“当前已经累加了多少和”
  • 当走到叶子节点时，再判断是否正好满足目标

这题至少有两种常见做法：

  • 解法一：递归 DFS（推荐）
  • 解法二：迭代 DFS / BFS 维护路径和

先理解：为什么一定要到叶子节点？

比如这棵树：

text
    1
   /
  2
 /
3

如果 targetSum = 3，那么：

  • 1 -> 2 的和确实是 3

但 2 不是叶子节点，因为它还有左孩子 3。

所以这条路径 不能算答案。

题目要求的是：

  • 一定要从根走到某个叶子
  • 然后整条路径和等于 targetSum

这个条件非常关键。

解法一：递归 DFS

这是这题最经典、最推荐掌握的做法。

思路拆解

递归时，我们可以把问题理解成：

text
当前节点要不要选？

其实当前节点一定在路径上，所以只需要：

  • 用 targetSum - node.val
  • 把“剩余需要凑出的和”传给子树

如果当前走到的是叶子节点，那么只要判断：

ts
node.val === targetSum

就知道这条完整路径是否满足要求。

也可以理解成：

  • 每往下走一层，就把当前节点值从目标和里减掉
  • 当走到叶子时，如果刚好减到 0，说明找到答案

一步一步写出算法

第一步：处理空树

如果根节点为空，肯定不存在路径。

ts
if (root === null) {
    return false
}

第二步：判断是否是叶子节点

ts
if (root.left === null && root.right === null) {
    return root.val === targetSum
}

如果已经走到叶子，就直接判断当前值是否等于剩余目标和。

第三步：递归左右子树

把当前节点值减掉后，继续去左右子树找。

ts
const remain = targetSum - root.val
return hasPathSum(root.left, remain) || hasPathSum(root.right, remain)

只要左边或右边有一条满足条件的路径，就返回 true。

代码实现（TypeScript）

ts
class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0
        this.left = left ?? null
        this.right = right ?? null
    }
}

function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if (root === null) {
        return false
    }

    if (root.left === null && root.right === null) {
        return root.val === targetSum
    }

    const remain = targetSum - root.val
    return hasPathSum(root.left, remain) || hasPathSum(root.right, remain)
}

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(h)

其中：

  • n 是节点总数
  • h 是树高
  • 递归调用栈最坏可能到 O(n)

这一解法的优缺点

优点：

  • 最自然
  • 代码最短
  • 最适合这题

缺点：

  • 依赖递归栈

解法二：迭代 DFS / BFS 维护路径和

这个做法的重点是：

  • 不用递归
  • 手动把“节点 + 当前路径和”一起存起来

这里我用 迭代 DFS 栈 来写，思想也同样适用于 BFS 队列。

思路拆解

每次遍历时，我们都需要知道两件事：

  • 当前在哪个节点
  • 从根到这个节点的路径和是多少

所以栈里可以存：

text
(node, currentSum)

每次弹出一个状态后：

  1. 如果当前是叶子节点，就检查 currentSum === targetSum
  2. 否则把左右孩子和更新后的路径和压入栈

这样也能完成同样的搜索。

一步一步写出算法

第一步：处理空树

ts
if (root === null) {
    return false
}

第二步：初始化栈

ts
const stack: Array<[TreeNode, number]> = [root, root](<root, root.val>)

这里的第二个值表示：

  • 从根走到当前节点的路径和

第三步：不断弹栈

ts
while (stack.length > 0) {
    const [node, sum] = stack.pop()!
    ...
}

第四步：如果当前是叶子，就判断答案

ts
if (node.left === null && node.right === null && sum === targetSum) {
    return true
}

第五步：压入左右孩子

如果左孩子存在：

ts
stack.push([node.left, sum + node.left.val])

如果右孩子存在：

ts
stack.push([node.right, sum + node.right.val])

最后如果整棵树都找完了还没成功，就返回 false。

代码实现（TypeScript）

ts
class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0
        this.left = left ?? null
        this.right = right ?? null
    }
}

function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if (root === null) {
        return false
    }

    const stack: Array<[TreeNode, number]> = [root, root](<root, root.val>)

    while (stack.length > 0) {
        const [node, sum] = stack.pop()!

        if (node.left === null && node.right === null && sum === targetSum) {
            return true
        }

        if (node.left !== null) {
            stack.push([node.left, sum + node.left.val])
        }

        if (node.right !== null) {
            stack.push([node.right, sum + node.right.val])
        }
    }

    return false
}

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

最坏情况下，栈里可能会存很多节点状态。

这一解法的优缺点

优点：

  • 不依赖递归
  • 更容易看清“节点 + 路径和”这个状态

缺点：

  • 代码比递归写法长一点

两种解法对比

解法时间复杂度空间复杂度特点
递归 DFSO(n)O(h)最自然，最推荐
迭代 DFSO(n)O(n)不用递归，更直观

如果你是第一次做这题，建议优先掌握递归版本。

手动模拟一遍递归解法

以经典例子为例：

text
root = [5,4,8,11,null,13,4,7,2,null,null,null,1]
targetSum = 22

从根节点 5 开始

还需要凑出的和：

text
22 - 5 = 17

走左边到 4

还需要凑出的和：

text
17 - 4 = 13

再走到 11

还需要凑出的和：

text
13 - 11 = 2

再走到叶子 2

此时：

text
2 - 2 = 0

而且 2 正好是叶子节点。

说明找到了一条满足条件的路径：

text
5 -> 4 -> 11 -> 2

所以返回 true。

面试时最容易错的点

1. 必须是“根到叶子”

这是最容易漏掉的条件。

不是任何一段路径都可以。

2. 中途和等于目标不一定算成功

一定要确认当前节点是不是叶子。

3. 空树返回 false

因为不存在从根到叶子的路径。

4. 递归时传的是“剩余目标和”

这个写法通常比“从上往下累加当前和”更简洁。

当然两种写法都可以。

一句话总结

这题的本质是：

沿着每一条根到叶子的路径搜索，并判断是否存在一条路径和等于 targetSum。

  • 想写标准解：用 递归 DFS
  • 想不用递归：用 迭代 DFS / BFS

推荐你最后记住的标准写法

如果你准备刷题，建议优先记下面这个递归版本：

ts
class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0
        this.left = left ?? null
        this.right = right ?? null
    }
}

function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if (root === null) {
        return false
    }

    if (root.left === null && root.right === null) {
        return root.val === targetSum
    }

    const remain = targetSum - root.val
    return hasPathSum(root.left, remain) || hasPathSum(root.right, remain)
}

因为这个版本：

  • 最贴合题意
  • 代码最短
  • 是这题公认的标准写法