124. 二叉树中的最大路径和（困难）

Blind 75 › 124. 二叉树中的最大路径和（困难） （第 10 章）
文章工具

题目

给定一棵二叉树，把「路径」定义为：从某个节点出发、沿树边连续走到另一个节点的节点序列；相邻节点必须直接相连，且同一个节点在路径中至多出现一次。路径至少包含一个节点，不要求经过根节点。

路径和就是路径上所有节点值的总和。请返回整棵树中任意路径的最大路径和。

自造示例：

         -30
       /    
      5     10
     /     / 
    1   4  6  -5

最优路径是 6 → 10，路径和为 16。注意它不经过根节点：若硬要带上根，6 + 10 + (-30) 会把结果拉成负数。

约束：节点数 1 ~ 3×104；节点值 -1000 ~ 1000。

思路

一句话：后序遍历，每个节点向上返回「不拐弯的最优单链」，同时在本节点结算「允许拐弯」的答案。

先想最直白的做法：枚举所有路径。树上任意两个节点之间只有唯一一条路径，枚举 n 个起点 × n 个终点会得到 O(n²) 条路径，每条路径再走一遍求和是 O(n)，总复杂度 O(n³)。n 最大 3×10⁴，完全不可行。

关键观察：任意一条路径都恰有一个「最高点」（离根最近的那个节点）。以最高点为界，路径最多向左走一段 + 向右走一段，绝不会再往上分叉。因此，只要知道每个节点左子树的最优单链、右子树的最优单链，就能在它这里拼出所有「以它为最高点」的路径。

于是把问题拆成两个量：

  • 单链（向上返回）：从当前节点出发、只朝一个方向走能得到的最大和，父节点只用它继续拼接。
  • 拐弯答案（本地结算）：root.val + 左单链 + 右单链，表示路径在当前节点拐弯，用全局变量取最大值。

自底向上的后序遍历正好满足「先算子树、再算父节点」。最后补一刀：单链如果是负数，选了只会拖累和，所以左右单链先和 0 取 max，把负贡献截断。

解法

一次后序 DFS 即可：

  1. 空节点返回 0。
  2. 递归得到左右子树单链，各自先与 0 取 max。
  3. 在本节点结算拐弯候选 root.val + left + right，更新全局答案。
  4. 向上返回单链 root.val + max(left, right)。

以自造示例的局部为例：

节点左单链右单链拐弯候选向上返回
5141+5+4=105+4=9
106max(-5,0)=06+10+0=1610+6=16
-30916-30+9+16=-5-30+16=-14

遍历过程中全局答案取到 16，来自节点 10 的「拐弯候选」。

下图把上面 4 个步骤串成流程，并逐步演示：

124. 二叉树中的最大路径和（困难） 解法步骤流程图
图① 解法步骤流程图（共 4 步）。
124. 二叉树中的最大路径和（困难） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right)
        : val(x), left(left), right(right) {}
};

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int ans = INT_MIN;                 // 全负节点时，答案是最大的那个单节点
        bestChain(root, ans);
        return ans;
    }

private:
    // 返回「不拐弯」的单链最大和；同时在 node 处结算「可拐弯」路径
    int bestChain(TreeNode* node, int& ans) {
        if (node == nullptr) return 0;     // 空子树贡献为 0

        int left = max(bestChain(node->left, ans), 0);    // 负分支直接截断
        int right = max(bestChain(node->right, ans), 0);

        int turnHere = node->val + left + right;           // 以 node 为最高点
        ans = max(ans, turnHere);

        return node->val + max(left, right);               // 只能选一边传给父节点
    }
};

Python

Python 3 示例