Binary Tree Maximum Path Sum


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

# Definition for a Binary Tree Node

Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

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

# Solution

# Recursive DFS

Let n be

class Solution:
    """
    @param root: The root of binary tree.
    @return: An integer
    """
    def maxPathSum(self, root):
        def dfs(root):
            if not root: return (-sys.maxsize, 0)

            left_max_sum, left_max_chain = dfs(root.left)
            right_max_sum, right_max_chain = dfs(root.right)
            max_sum = max(left_max_sum, right_max_sum, left_max_chain + right_max_chain + root.val)
            max_chain = max(max(left_max_chain, right_max_chain) + root.val, 0)
            return (max_sum, max_chain)
        return dfs(root)[0]