Problem statement

https://binarysearch.com/problems/Largest-Tree-Sum-Path/

Solution

Equal to Leetcode 0124. Binary Tree Maximum Path Sum.

Complexity

It is O(n) for time and O(h) for space.

Code

class Solution:
    def solve(self, root):
        self.ans = -float("inf")
        
        def dfs(node):
            if not node: return [0, 0]
            l1, r1 = dfs(node.left)
            l2, r2 = dfs(node.right)
            l, r = max(l1, r1, 0) + node.val, max(l2, r2, 0) + node.val
            self.ans = max(self.ans, l + r - node.val)
            return [l, r]
            
        dfs(root)
        return self.ans