[LeetCode] 124. Binary Tree Maximum Path Sum

Problem : https://leetcode.com/problems/binary-tree-maximum-path-sum/

On each node,  its path sum = Max( node,  node + left_path, node  + right_path, node + left_path + right_path)

Use postorder traversal to find the 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:
    def maxPathSum(self, root: TreeNode) -> int:
        self.result = -1000
        
        def postOrder(node):
            
            if node.left and node.right:
                left = postOrder(node.left)
                right = postOrder(node.right)
                
                self.result = max(self.result, node.val + left + right, node.val + left, node.val + right, node.val)
                
                return max(node.val + left, node.val + right, node.val)
            
            if node.left:
                left = postOrder(node.left)
                
                self.result = max(self.result, node.val + left, node.val)
                
                return max(node.val + left, node.val)
            
            if node.right:
                right = postOrder(node.right)
                
                self.result = max(self.result, node.val + right, node.val)
                return  max(node.val + right, node.val)
            
            self.result = max(self.result, node.val)
            return node.val
        
        if root:
            postOrder(root)
        
        
        return self.result