Binary Tree Maximum Path Sum
A path is any sequence of connected nodes, each used at most once, and it need not pass through the root. Return the maximum sum of any path.
A way to picture it
Hikers score points on a mountain trail network. Each junction asks its two trails how many points they can add, ignoring any trail that would lose points. It records the best hike that bends through itself — but it can only recommend ONE trail to the junction above it.
How to approach it
gain(node) = node + max(0, gain(left), gain(right)) is what a node offers its parent. At each node, also try node + left + right as a candidate answer.
Example
Input: {"root":[1,2,3]}. Output: 6.
Complexity: O(n) time and O(h) space. One post-order pass.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.