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 """
 6 from dataclasses import dataclass
 7 
 8 
 9 @dataclass
10 class T:
11     val: int
12     left: int = None
13     right: int = None
14 
15 
16 class 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 
30 t = T(-10, T(9), T(20, T(15, T(5)), T(7)))
31 
32 print(Solution().maxPathSum(t))