[124][困难][DFS] 二叉树中的最大路径和

题目描述

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

给定一个非空二叉树，返回其最大路径和。

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

示例 1：

输入：[1,2,3]

       1
      / \
     2   3

输出：6

示例 2：

输入：[-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出：42

解题思路

本题的关键在于理解题目所说的路径. 路径首先是着眼于某一个节点(对应题目中路径被定义为一条从树中任意节点出发), 然后对于左右子树, 从中各找到一条普通意义的路径, 即从这个结点开始, 向下连接, 形成一条可以有曲折但不能有分叉的连线, 可以在任何一个位置停止.

因此本体中的路径, 只能在开始的节点处分叉, 可以由左右两条连线组成, 也可以只有一条, 或仅仅只有一个节点组成.

如其他的路径问题一样, 使用DFS解决问题. 对于每个节点, 计算这个节点所有可能路径的最大值, 需要考虑节点值, 左右子树的连线, 判断左右子树递归返回的连线最大值是否大于0, 大于0则可以包含这条路径, 否则抛弃. 计算得到这个节点的最大路径之后, 与全局的进行比较, 保存更大的值.

在计算节点路径值的时候, 要求左右子树返回的是最长连线值, 而不是最长路径, 因为对于当前节点, 在左右子树中不能再有分叉, 只能使用连线. 因此DFS递归函数, 返回的是连线值. 连线值就考虑的是节点本身, 以及左右子树中连线的较大值, 如果这个较大值大于0, 需要与节点本身组成更长的连线, 一起返回, 否则, 只返回节点本身的值即可.

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        def max_gain(node):
            nonlocal max_sum
            if not node:
                return 0

            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)

            price_newpath = node.val + left_gain + right_gain
            max_sum = max(max_sum, price_newpath)

            return node.val + max(left_gain, right_gain)

        max_sum = float('-inf')
        max_gain(root)
        return max_sum