题解 | #二叉树的最大路径和#

递归函数的意义：以root为终点的路径中，最大的path sum值。
后序遍历，因为要先求左右结点的path sum值。

# 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 ):
        # write code here
        self.res = float("-inf")
        def postOrder(root):
            # 以root为end的路径中最大的path sum
            if not root:
                return 0
            leftMax = postOrder(root.left)
            rightMax = postOrder(root.right)
            curr = root.val
            if leftMax > 0:
                curr += leftMax
            if rightMax > 0:
                curr += rightMax
            self.res = max(self.res, curr)
            return max(root.val, max(leftMax, rightMax) + root.val)

        postOrder(root) 
        return self.res