Problem statement

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

Solution

This problem is very similar to problem 543 Diameter of Binary Tree, the idea is very similar here, do recursion, and keep 2 numbers in each node: left_max, right_max, I am not sure why it is marked as hard.

Complexity

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

Code

class Solution:
    def maxPathSum(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