A path in a binary tree is a run of nodes where each node is joined to the next by an edge, and no node is used twice. It can start and end at any node, it does not have to pass through the root, and it may be a single node. Its sum is the total of the values on it.
Given the root of a binary tree, return the largest sum of any path.
The path 5 → 8 → 7 turns at 8 and never touches the root. Climbing on up to 2 would trade the 7 for 2 and give only 15.
The path 4 → -1 → 5 → 3 crosses a negative node, because the values behind it make up for it.
Every value is negative, so the best path is the single node -2. A path always holds at least one node, so the answer can't be 0.
Constraints
1 and 3 × 10⁴ nodes.-1000 <= Node.val <= 1000Every path has a highest node, where it turns. From there it goes down at most one branch on each side. Work out the best path that turns at each node, and keep the largest.
Hold any path up by its highest node, the one closest to the root. The path turns there: from the turning node it goes down into the left subtree for a while, and down into the right subtree for a while, and either side may be empty. It can't turn anywhere else: once a path steps down from a node to its child, it can never climb again, because the only way up from that child is the edge it just came down, and no node is used twice.
Time O(n)Space O(h)
The full walkthrough and code are part of Premium
20