[Hard] 124. Binary Tree Maximum

Description

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:

Solution

分治法。
需要考虑的是，子树中最大的路不一定必过根节点。所以要记录single Path的值。
计算树的最长path有2种情况：

1. 通过根的path.

(1)如果左子树从左树根到任何一个Node的path大于零，可以链到root上

(2)如果右子树从右树根到任何一个Node的path大于零，可以链到root上

2. 不通过根的path. 这个可以取左子树及右子树的path的最大值。

所以创建一个inner class:

记录2个值：

1. 本树的最大path。

2. 本树从根节点出发到任何一个节点的最大path.

当root == null,以上2个值都要置为Integer_MIN_VALUE; 因为没有节点可取的时候，是不存在solution的。以免干扰递归的计算

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

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        maxSum, _ = self.maxPathHelper(root)
        return maxSum
        
    def maxPathHelper(self, root):
        if root is None:
            return -float("inf"), 0
        
        left = self.maxPathHelper(root.left)
        right = self.maxPathHelper(root.right)
        maxpath = max(left[0], right[0], root.val + left[1] + right[1])
        single = max(left[1] + root.val, right[1] + root.val,0)
        
        return maxpath, single