A path is any sequence of connected nodes, used at most once each, and it does not have to pass through the root. Return the largest possible sum of a path.
DSA Animator › DSA Revision › Tree › Binary Tree Maximum Path Sum
Remember: record the bending path, but return a single branch. Clamp negative gains to 0. The video solves Binary Tree Maximum Path Sum (LeetCode 124, Hard) with the DFS Gain pattern from the Tree topic, and you can replay every step in the interactive Binary Tree Maximum Path Sum animation.
A path is any sequence of connected nodes, used at most once each, and it does not have to pass through the root. Return the largest possible sum of a path.
For the tree minus 10, with children 9 and 20, where 20 has children 15 and 7, the answer is 42. The best path is 15, 20, 7.
Trying every pair of end points and summing the path between them is far too slow. Instead, each node can report the best downward path it can offer to its parent.
Define the gain of a node as its value plus the better of its two downward gains. A negative gain only hurts, so treat it as 0. At each node, the best path that bends here is its value plus the left gain plus the right gain. Update a global best with that bending path. But return only one side to the parent, because a path cannot split in two.
The leaves 15 and 7 have gains 15 and 7. At 20, the bending path is 20 plus 15 plus 7, which is 42, and the best becomes 42. Node 20 returns 20 plus 15, which is 35, to its parent. The leaf 9 returns 9. At the root, the bending path is minus 10 plus 9 plus 35, which is 34. 34 is less than 42, so the best stays 42. The answer is 42.
In code, keep a field best, starting at the smallest integer. The gain function returns 0 for null. It takes the larger of 0 and each child gain, updates best with value plus left plus right. Then it returns value plus the larger of left and right. Each node is visited once, so it's O of n time.
Remember: record the bending path, but return a single branch. Clamp negative gains to 0.