T124.二叉树中的最大路径和

dfs, dp, binary tree, https://leetcode.cn/problems/binary-tree-maximum-path-sum/

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

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

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

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

树中节点数目范围是 [1, 3 * 10^4]
-1000 <= Node.val <= 1000

这道题是二叉树题目中的经典困难题。我们需要寻找二叉树中任意两个节点之间路径的最大和。

解题思路

路径的定义：
- 在二叉树中，对于任意一个节点 $u$ ，经过它的最大路径有几种可能：
  1. 节点 $u$ 本身。
  2. $u$ 加上左子树向下延伸的一条路径。
  3. $u$ 加上右子树向下延伸的一条路径。
  4. $u$ 加上左子树向下延伸的一条路径，再加上右子树向下延伸的一条路径（此时 $u$ 是路径的最高点/转折点）。
递归函数设计：
- 我们需要一个递归函数 maxGain(node)，它的作用是：计算从当前节点开始，向其子树延伸所能获得的最大路径和。
- 注意：为了能与父节点连接，这个函数只能选择左子树或右子树中的一条路径，或者是只选当前节点。
- 在递归的过程中，我们顺便计算以当前节点为转折点的路径总和，并更新全局最大值。
状态转移：
- 对于节点 node，它能提供的最大增益为：node.val + max(maxGain(node.left), maxGain(node.right), 0)。
- 如果子树的增益是负数，我们宁愿不选（即与 0 取 max）。
- 在每个节点处，更新全局最大值 self.max_sum = max(self.max_sum, node.val + left_gain + right_gain)。
代码实现

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        # 初始化全局最大值为负无穷
        self.max_sum = float('-inf')

        def get_max_gain(node):
            if not node:
                return 0
            
            # 递归计算左右子节点的最大增益
            # 如果增益小于 0，则忽略该子树（取 0）
            left_gain = max(get_max_gain(node.left), 0)
            right_gain = max(get_max_gain(node.right), 0)
            
            # 当前节点作为路径最高点（转折点）时的路径和
            current_path_sum = node.val + left_gain + right_gain
            
            # 更新全局最大路径和
            self.max_sum = max(self.max_sum, current_path_sum)
            
            # 返回该节点能提供给父节点的最大增益
            # 只能选择左或者右中的一条，或者是只选节点本身
            return node.val + max(left_gain, right_gain)

        get_max_gain(root)
        return self.max_sum

复杂度分析

时间复杂度： $O (N)$ ，其中 $N$ 是二叉树中的节点个数。我们需要遍历每个节点恰好一次。
空间复杂度： $O (H)$ ，其中 $H$ 是二叉树的高度。这是递归调用的栈空间开销。最坏情况下（树呈链状），空间复杂度为 $O (N)$ 。

关键点总结

全局变量：需要一个变量在递归过程中不断记录遇到的“最大路径和”。
向上返回 vs. 局部更新：递归函数返回的是“单边”的最大和（为了供上层节点使用），而更新全局变量时使用的是“双边”的最大和（将当前节点视为路径的顶点）。
负值处理：通过 max(gain, 0) 过滤掉会让路径和变小的负数分支。

T124.二叉树中的最大路径和 ​

T124.二叉树中的最大路径和