Maximum path sum
Every node of a binary tree holds an integer, and some values may be negative. A path is a chain of nodes in which each node is the parent or a child of the next one, and no node appears twice: you could trace it along the edges in one pen stroke. A path has at least one node. It can start and end anywhere, so it does not have to pass through the root or end at a leaf (a node with no children). Adding up the values on a path gives its path sum.
The tree has at least one node. Return the largest path sum over all of its paths.
A path cannot branch. In the tree [1, 2, None, 3, 4], the root 1 has a left child 2, and 2 has children 3 and 4. The nodes 3, 2, 4 form a path, and so do 3, 2, 1. No path holds all four nodes: it would need three branches meeting at the 2.
Trees in the examples are written in level order, the way build_tree reads them: the root, then each row from left to right, with None where a child is missing.
root = [2, -1, 3]Output5The path 2, 3 sums to 5. Stretching it to the -1 on the other side would give 4.
root = [-5, 4, 8, None, None, -2, 6]Output14The path 8, 6 sums to 14. Climbing through the root to reach the 4 as well gives 4 - 5 + 8 + 6 = 13, which is less.
root = [-3, -7, -1]Output-1Every value is negative, so the best path is the single node -1.
1 ≤ number of nodes ≤ 3 × 104
-1,000 ≤ node value ≤ 1,000
The tree is at most 500 levels deep, so a recursive solution fits under plain Python's default of about 1,000 nested calls.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.