LC124 Binary Tree Maximum Path Sum

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # main idea: do post order traversal and caculate current case1,2,3  max path and keep updating it 
    #              case 1:  node              case2,3    node     or  node         
    #                       / \                          /              \
    #                    left right                    left             right
    #             soluton for case1: lrr = left + right + node.val       solution for case2,3:  lr_max =max(left,right) + node.val;   post order
    # time O(N)  space O(1) if not considering recursion depth 
    def maxPathSum(self, root: TreeNode) -> int:
        maxSum = [root.val]
        def maxSubPath(node,maxSum):
            if not node:
                return 0
            left = max(0, maxSubPath(node.left,maxSum))  # here in order to maximize the sum, need to avoid  negtive node because it's better not move at all(path = 0). 
            right = max(0, maxSubPath(node.right,maxSum))
            lrr = left + right + node.val
            lr_max = max(left,right) + node.val
            maxSum[0] = max(maxSum[0],max(lr_max,lrr))
            return lr_max # return max one side sub path to parent node 
        maxSubPath(root,maxSum)
        return maxSum[0]