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))