Problem context and objectives
Mission briefing
Archive pathfinder · Clues branch through a living archive
Explore only the branches that can still contain the answer: The Maximum Tree Path.
Ignoring the parent-child rule turns a focused search into a full maze traversal.
How you win
- 1Recognize when Binary tree maximum path sum matches the clues
- 2Keep this true after every move: gain(node) is the best nonnegative-extended path starting at node, while answer is the best complete path seen
- 3Reach the result within O(n) time and O(height) space
Rules and pressure
- Target cost: O(n) time and O(height) space
- State rule: gain(node) is the best nonnegative-extended path starting at node, while answer is the best complete path seen
Lesson 1 of 3
Score a complete path with both positive arms at every node, then return only the better single arm to the parent.
Separate the two-arm score from the one-arm return at one node.
Your call · At node 20, what are the complete-path score and upward gain?