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

题目

• 题号：124
• 难度：困难
• https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root，返回其 最大路径和 。

实现

思路1 递归

通过题目可以发现，对于二叉树每个节点有两个分支，我们要找到最大路径和，就是要找到某个节点node，以node作为根节点，左右两个子树的最大路径和加上node本身的值是最大的。
因此定义一个函数f(node)，用来计算以node为起点的一条路径的最大路径和。即递归结构为f(node) = node + max(f(left), f(right))。然后我们自顶向下递归，直到叶子节点（路径和为其本身），不断更新存储最大路径和的变量。
尤其注意这里的递归结构计算的是一条路径的最大路径和，而不是计算树的最大路径和。举个例子，

    20
   / \
  6  10
    /  \
   12   5

我们会让树的左子树6去计算一个路径的最大路径和leftScore，即为6；然后让树的右子树10去计算一个路径的最大路径和，即rightScore = f(10) = 10 + max(12, 5) = 22（右子树的最大路径为）。
所以此时我们得到了这个树左右两条都是最大的路径，那么就计算一下这两条路径组合后的最大路径和为 score = leftScore + rightScore + root = 6+22+20 = 48。
上述过程会对每个节点执行，因此会得到以每个节点为根节点时的最大路径和，通过一个变量去维护它，最后输出这个变量即可。

最终代码为：

# 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 __init__(self):
        self.score = float("-inf")
    def maxPathSum(self, root: TreeNode) -> int:
        def maxScore(root):
            if not root:
                return 0
            # 若子节点路径和为负，则直接抛弃这个子节点
            leftScore = max((maxScore(root.left), 0))
            rightScore = max((maxScore(root.right), 0))
            # 更新记录的最大路径和
            pathScore = root.val + leftScore + rightScore
            self.score = max(pathScore, self.score)
            # 注意该函数返回的只是单个路径和
            return root.val + max(leftScore, rightScore)
        maxScore(root)
        return self.score

时间复杂度：。n是树中节点的总数。
空间复杂度：。取决于递归调用的层数，最大层数等于树的高度，而最坏情况下树高度为其节点数。