A path in a binary tree is a sequence of distinct nodes where each consecutive pair is joined by an edge (parent to child or child to parent). It has at least one node and doesn't have to pass through the root. Its sum is the total of its node values.
Write max_path_sum(root: TreeNode) -> int: the largest path sum in the tree. TreeNode(val, left=None, right=None) is in the starter. Values may be negative.
Examples:
2
/ \
-1 6
/ \
5 7
max_path_sum(root) == 18, from the path 5 -> 6 -> 7. The root can't be added: 6 would then need three path neighbours.
- A single node
-4gives-4(the path must be non-empty). TreeNode(-3, TreeNode(8), TreeNode(-1))gives8.
Constraints: 1 to about 70,000 nodes, values -1000..1000. The tree can be lopsided, up to a few thousand levels deep (the Python tests raise the recursion limit for you). Aim for O(n).
Show hint
Every path has one highest node where it bends. For each node, what does it need from each child, and what should it hand up to its parent (a path that continues upward can't bend there)? Keep the overall best on the side.