跳至主要內容

LeetCode 124. 二叉树中的最大路径和

Skyme2026/8/13大约 9 分钟刷题Hot 100二叉树深度优先搜索 DFS后序遍历递归

LeetCode 124. 二叉树中的最大路径和

题目核心

二叉树中的路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

路径和是路径中各节点值的总和。

给你一个二叉树的根节点 root，返回其最大路径和。

例如：

    -10
    /  \
   9    20
       /  \
      15   7

最大路径和：15 + 20 + 7 = 42
路径是 15 → 20 → 7，把 20 当成"最高点"拐弯

解题思考过程

第一步：先理解"路径"的形状

路径可以是任意两个节点之间的通路，不一定从上往下。它可以在某个节点拐弯，形成 ∧ 形：

     A
    / \
   B   C
  /     \
 D       E

路径 D→B→A→C→E 是合法的：经过 B 往上走到 A，再往下拐到 C，最后走到 E。路径和是 D+B+A+C+E。

但不能有分叉——比如 D→B→A 同时再走 B→另一个方向，这会让 B 出现两次，不合法。

所以任意一条路径一定有一个唯一的最高点（拐弯点），路径从它的左侧子树某节点上来、经过它、再下到右侧子树某节点上去。这个最高点就是路径上深度最小（最靠近根）的那个节点。

第二步：暴力做法行不通

最朴素的思路：枚举所有可能的节点对（起点、终点），求它们之间路径的和，取最大。

  • 节点对数量 O(n²)
  • 每条路径求和 O(n)
  • 总共 O(n³)

肯定超时。

第三步：把路径拆成三部分

根据"路径有唯一最高点"这个观察，路径 P 以节点 X 为最高点时的路径和可以拆成：

路径和 = 左子树能往上贡献的最大和 + X.val + 右子树能往上贡献的最大和

其中"往上贡献的最大和"定义为：从这个子节点出发，一直往下走，能拿到的最大路径和（只能选左或右其中一边走，不能两边都选——因为如果两边都选，子节点就成了最高点，就不再是对父节点的贡献了）。

这就是关键：一个节点作为子节点回答父节点时，只能汇报"以我为起点、向下走一条链的最大和"，因为父节点本身还要作为更高的路径的一部分。

第四步：负数贡献要不要？

如果某个子节点向下能拿到的最大贡献是负数，比如左子树最大贡献是 -5，那加上它只会让总和更小。

所以可以用一个小技巧：负贡献就当它不存在，取 max(0, 贡献)，意思是不选这一边。

这样就相当于：左/右子树如果对总和有正贡献就加上，否则就不加——路径从当前节点开始就行，不需要往负数那边走。

第五步：DFS 的返回值和 ans 是两件事

这是本题最容易混乱的地方：

  • dfs(node) 的返回值：给父节点用的，回答"以 node 为起点，向下一条链的最大和"——所以只能 node.val + max(l, r)，不能两边都加。
  • 全局 ans：记录所有"以某个节点为最高点"的路径和中的最大值——所以是 l + node.val + r，两边都加，因为 node 是最高点、路径在这里拐弯。

第六步：递推顺序

因为要先知道左右子树的结果，才能计算当前节点的贡献和作为最高点的路径和，所以 DFS 是后序遍历：先左，再右，再处理当前节点。

第七步：边界

空节点对父节点没有任何帮助，贡献 0。

当前解法：后序 DFS + 全局最大值

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function (root) {
  let ans = -Infinity;

  const dfs = (root) => {
    if (root === null) {
      return 0;
    }

    // 左右子树能给当前节点提供的最大贡献
    let l = Math.max(0, dfs(root.left));
    let r = Math.max(0, dfs(root.right));

    // 当前节点作为路径的"最高点"
    ans = Math.max(ans, l + root.val + r);

    // 返回给父节点时，只能选左边或右边其中一条
    return root.val + Math.max(l, r);
  };

  dfs(root);

  return ans;
};

代码逐行解释

全局答案

let ans = -Infinity;

用一个全局（外层函数作用域）变量保存遍历过程中遇到的最大路径和。初始值设为 -Infinity，而不是 0，原因是：节点值可能全是负数（比如只有一个节点 -3），最大路径和就是 -3，如果初始为 0 就会被错返回 0。

DFS 递归函数

const dfs = (root) => {

dfs(node) 的语义是：返回以 node 为起点，只能顺着子节点向下走一条链，能拿到的最大路径和。

这个返回值是给 node 的父节点用的——父节点要把自己当最高点时，需要知道左/右孩子能往上贡献多少。

空节点终止条件

if (root === null) {
  return 0;
}

空节点对父节点没有任何贡献——相当于父节点的那一侧"没有子节点"，所以返回 0。这个 0 和下面 Math.max(0, ...) 的设计正好配合。

拿到左右子树贡献

let l = Math.max(0, dfs(root.left));
let r = Math.max(0, dfs(root.right));

先递归求左右子树。注意关键的 Math.max(0, ...)：

  • 如果子树贡献是正数，就带上，让路径和更大。
  • 如果子树贡献是负数，就把它当成 0，意思是不往那一边走——从当前节点直接开始就好，比"去负数那边兜一圈"强。

这是 DFS 后序的典型写法：先左，再右，最后处理当前节点。

当前节点作为最高点，更新 ans

ans = Math.max(ans, l + root.val + r);

这里是最核心的一行。当 root 作为路径的"最高点"（拐弯点），路径可以是：

左子树某节点 → ... → root.left → root → root.right → ... → 右子树某节点

所以路径和就是"左边最大链 + 当前节点 + 右边最大链"，即 l + root.val + r。

把它和 ans 对比，如果更大就更新。因为每个节点都会当一次"最高点候选"，遍历完后 ans 就覆盖了所有可能的路径形状。

返回给父节点的贡献

return root.val + Math.max(l, r);

这里不能两边都加，只能选左或右。因为父节点还要当它自己所在路径的一部分：从父节点的视角往下看，root 只能出现在路径的"左边那一条链"或"右边那一条链"里，不能同时出现在两边——否则路径在 root 这里就分叉了，不合法。

所以返回：当前节点值，加上左/右贡献较大的那一边。

开始遍历并返回结果

dfs(root);
return ans;

从根节点开始后序 DFS，过程中所有节点都更新了一次 ans，最后 ans 就是整棵树中的最大路径和。

执行过程示例

以题目中最经典的例子：

    -10
    /  \
   9    20
       /  \
      15   7

逐步模拟：

dfs(-10)
├── dfs(9)
│   ├── dfs(null) → 0，l = max(0, 0) = 0
│   ├── dfs(null) → 0，r = max(0, 0) = 0
│   ├── ans = max(-∞, 0+9+0) = 9
│   └── return 9 + max(0, 0) = 9
├── dfs(20)
│   ├── dfs(15)
│   │   ├── dfs(null) → 0，l = 0
│   │   ├── dfs(null) → 0，r = 0
│   │   ├── ans = max(9, 0+15+0) = 15
│   │   └── return 15 + max(0, 0) = 15
│   └── dfs(7)
│       ├── dfs(null) → 0，l = 0
│       ├── dfs(null) → 0，r = 0
│       ├── ans = max(15, 0+7+0) = 15
│       └── return 7 + max(0, 0) = 7
│   // 回到节点 20
│   ├── l = max(0, 15) = 15
│   ├── r = max(0, 7) = 7
│   ├── ans = max(15, 15+20+7) = 42
│   └── return 20 + max(15, 7) = 35
├── // 回到节点 -10
│   l = max(0, 9) = 9
│   r = max(0, 35) = 35
│   ans = max(42, 9 + (-10) + 35) = 42  ← 34 < 42，不更新
│   return -10 + max(9, 35) = 25

最终 return ans = 42

和预期一致：15 + 20 + 7 = 42，最大路径就是 15 → 20 → 7。

一个容易混乱的点：为什么 ans 在 dfs 里更新，而不是直接 return dfs？

因为：

  • dfs(root) 回答的是"以 root 为端点向下走的最大链"——它只是一条链，路径没有拐弯。根节点的 return 值 25（上面例子中）不是答案，因为它只是 -10 + 35，是根向右侧延伸的一条链的和。
  • 真正的最大路径（42）是以 20 为最高点、左右都包含的拐弯路径。这种"拐弯"路径不可能作为任何节点的父节点贡献值返回，必须用独立的全局变量 ans 在 dfs 内部顺手记录。

简单说：return 用于"对父节点汇报一条链"，ans 用于"偷瞄当前节点当最高点的拐弯路径"。两者记录的对象完全不同。

负节点的例子

再验证一个全负节点的边界：

    -3
   /  \
null  null

执行：

dfs(-3):
  l = max(0, dfs(null)) = 0
  r = max(0, dfs(null)) = 0
  ans = max(-∞, 0 + (-3) + 0) = -3
  return -3 + max(0, 0) = -3

最终 return ans = -3，正确。

这也是为什么 ans 初始要是 -Infinity，不能是 0。

复杂度分析

  • 时间复杂度：O(n)。每个节点恰好访问一次。
  • 空间复杂度：O(h)，h 是树高。递归栈最多等于树的高度。
    • 对于平衡树：h ≈ log n
    • 最坏情况退化成链：h = n

易错点

  1. ans 初始值不是 0，而是 -Infinity：全是负数节点时，最大路径和也是负数，初始为 0 会错。

  2. 子树贡献要 max(0, dfs(...))：负贡献的子树不选，否则会把节点本身的值拖累得更小。比如节点值 5，左子树最大贡献 -2，总路径 5-2+右 就不如 5+右 好。

  3. return 里只加一边（Math.max(l, r)），不是两边都加：两边都加意味着在当前节点拐弯，那就是当前节点作为最高点的路径和——应该算到 ans 里，而不是返回给父节点。返回给父节点必须是一条链，只能选左右一边。

  4. 路径至少包含一个节点：题目明确"路径至少包含一个节点"。代码中 l + root.val + r 就算 l=r=0（左右都不选，负贡献裁掉）也至少包含 root.val 本身，符合要求。

路的尽头依旧是路
Copyright © 2026 Skyme