hard
Question
寻找二叉树的最大路径和，路径可以起始和终止与树的任意节点，可以不经过根节点。
假设二叉树不空，如果只有一个节点，则起始节点和终止节点都为该节点。
倘若所有节点都是负数，则寻找最大负数节点。
Example
最大路径和10
最大路径和6
使用bottom-up可以有效节约重复计算
对于某个节点，可能的最大路径和只能是下面情况中的一种
- max(left subtree) + node
- max(right subtree) + node
- max(left subtree) + max(right subtree) + node
- 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
