二叉树中的最大路径和

问题简述

求给定二叉树中的最大路径和。
路径定义：
    1. 同一个节点在路径中最多出现一次；
    2. 路径至少包含一个节点，可以不经过根节点；

二叉树中的最大路径和_牛客题霸_牛客网

思路：DFS

• 定义函数 maxGain(node) 表示以 node 为起点的最大路径；显然 maxGain 可以通过递归计算（详见代码）；

• 则经过 node 的最大路径和，可以表示为 node.val + maxGain(node.left), maxGain(node.right)；因此可以在计算 maxGain(root) 的过程中，记录经过每个节点的最大路径和，进而得到全局最大路径。

Python

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型
#
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        # write code here

        self.ret = float('-inf')

        def maxGain(node):
            if not node: return 0

            # 如果子路径的 maxGain 为负数，那么对 node 来说 maxGain 就是自己本身；
            max_left = max(0, maxGain(node.left))
            max_right = max(0, maxGain(node.right))
            # 记录“经过”node 节点的最大路径
            self.ret = max(self.ret, node.val + max_left + max_right)
            return node.val + max(max_left, max_right)  # 至少要包含自己本身

        maxGain(root)
        return self.ret