二叉树中的最大路径和

题目链接 · 灵神原题解（署名来源）

视频讲解

递归原理：深入理解递归【基础算法精讲 09】。

本题视频讲解：树形 DP【基础算法精讲 23】，制作不易，欢迎点赞关注~

视频内容补充

本题有两个关键概念：

链：从下面的某个节点（不一定是叶子）到当前节点的路径。把这条链的节点值之和，作为 $dfs$ 的返回值。如果节点值之和是负数，则返回 $0$ （和 $0$ 取最大值）。这个思想和 53. 最大子数组和是一样的，如果左侧子数组的元素和是负数，就不和当前元素拼起来。
直径：等价于由两条（或者一条）链拼成的路径。我们枚举每个 $node$ ，假设直径在这里「拐弯」，也就是计算由左右两条从下面的某个节点（不一定是叶子）到 $node$ 的链的节点值之和，去更新答案的最大值。

⚠注意： $dfs$ 返回的是链的节点值之和，不是直径的节点值之和。

答疑

问：如果所有节点值都是负数，代码会算出什么结果？

答：在所有节点值都为负数的情况下，代码中的 ans = max(ans, sum_l + node.val + sum_r) 等价于 ans = max(ans, node.val)，我们求的是最大节点值（绝对值最小的负数）。这是符合题目要求的，因为在所有节点值都为负数的情况下，路径只有一个节点是最优的（毕竟节点越多，元素和越小）。类比 53. 最大子数组和，当数组元素都是负数的时候，答案就是 $max (nums)$ 。

Python 解法1C++ 解法1

python

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        ans = -inf

        def dfs(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0  # 没有节点，和为 0
            sum_l = dfs(node.left)  # 左子树最大链和
            sum_r = dfs(node.right)  # 右子树最大链和
            nonlocal ans
            ans = max(ans, sum_l + node.val + sum_r)  # 左链 + node + 右链 = 路径
            return max(max(sum_l, sum_r) + node.val, 0)  # 当前子树最大链和（注意这里和 0 取最大值了）

        dfs(root)
        return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int ans = INT_MIN;

        auto dfs = [&](this auto&& dfs, TreeNode* node) -> int {
            if (node == nullptr) {
                return 0; // 没有节点，和为 0
            }
            int sum_l = dfs(node->left); // 左子树最大链和
            int sum_r = dfs(node->right); // 右子树最大链和
            ans = max(ans, sum_l + node->val + sum_r); // 左链 + node + 右链 = 路径
            return max(max(sum_l, sum_r) + node->val, 0); // 当前子树最大链和（注意这里和 0 取最大值了）
        };

        dfs(root);
        return ans;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是二叉树的节点个数。
空间复杂度： $O (h)$ ，其中 $h$ 是二叉树的高度。递归需要 $O (h)$ 的栈空间。

课上题目

课后作业

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

视频讲解 ​

视频内容补充 ​

答疑 ​

复杂度分析 ​

课上题目 ​

课后作业 ​

分类题单 ​