124. Binary Tree Maximum Path Sum

Solution 1: DFS + Recursive

# 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 __init__(self):
        self.maxPathSumInHistory = -2147483648
        
    def dfs(self, root):
        if not root:
            return 0
        
        lftMaxPathSum = max(self.dfs(root.left), 0)
        rhtMaxPathSum = max(self.dfs(root.right), 0)
        curPathSum = root.val + lftMaxPathSum + rhtMaxPathSum
        
        self.maxPathSumInHistory = max(self.maxPathSumInHistory, curPathSum)
        return root.val + max(lftMaxPathSum, rhtMaxPathSum)
        
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.dfs(root)
        return self.maxPathSumInHistory

Time Complexity: O(N)
Space Complexity: O(N) // Call stack of recursion

Solution 2: DFS + Iterative

Time Complexity: O(N)
Space Complexity: O(N)

Reference

https://leetcode.com/problems/binary-tree-maximum-path-sum/discuss/603423/Python-Recursion-stack-thinking-process-diagram