python实现leetcode之124. 二叉树中的最大路径和

解题思路

定义一个辅助函数返回两个值：
1.只包含一个方向（左右）的最大路径
2.包含两个方向（左和右）的最大路径
由于至少包含一个节点，所以如果ls和rs都是0时，必须包含当前节点
total取局部最大值。但也是必须要包含节点的

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

代码

# 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
        """
        return m(root)[1]


def m(tree):
    """
    single: 只包含一个方向（左右）的最大路径
    total : 包含两个方向（左和右）的最大路径
    """
    if not tree: return 0, 0
    ls, lt = m(tree.left)
    rs, rt = m(tree.right)
    single = tree.val+max(0, ls, rs)
    if ls > 0 and rs > 0:
        total = tree.val + ls + rs
    else:
        total = single
    if tree.left and lt > total: total = lt
    if tree.right and rt > total: total = rt
    return single, total