hard

Question

寻找二叉树的最大路径和，路径可以起始和终止与树的任意节点，可以不经过根节点。
假设二叉树不空，如果只有一个节点，则起始节点和终止节点都为该节点。
倘若所有节点都是负数，则寻找最大负数节点。

Example

最大路径和10

最大路径和6

使用bottom-up可以有效节约重复计算
对于某个节点，可能的最大路径和只能是下面情况中的一种

1. max(left subtree) + node
2. max(right subtree) + node
3. max(left subtree) + max(right subtree) + node
4. node

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

class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.maxSum = 0
        self.findMax(root)
        return self.maxSum
        
    def findMax(self, p):
        if not p:
            return 0
        left = self.findMax(p.left)
        right = self.findMax(p.right)
        self.maxSum = max(p.val+left+right, self.maxSum)
        res = p.val + max(left, right)
        return res if res > 0 else 0