binary tree maximum path sum

🏠

Incredible algorithm, and somewhat reminiscent of [[kadane's algorithm]], but for binary trees.

 1"""
 2           1
 3         /   \
 4     2         3
 5"""
 6from dataclasses import dataclass
 7
 8
 9@dataclass
10class T:
11    val: int
12    left: int = None
13    right: int = None
14
15
16class Solution:
17    def maxPathSum(self, root):
18        def max_path(n):
19            if not n:
20                return 0
21            l, r = max_path(n.left), max_path(n.right)
22            self.max = max(self.max, l + n.val + r)
23            return max(n.val + max(l, r), 0)
24
25        self.max = float('-inf')
26        max_path(root)
27        return self.max
28
29
30t = T(-10, T(9), T(20, T(15, T(5)), T(7)))
31
32print(Solution().maxPathSum(t))