Binary Tree Maximum Path Sum
Binary Tree Maximum Path Sum is a hard Trees problem from the Blind 75. The key pattern is post-order dfs with a global best, and a good solution runs in O(n) time.
Problem
Return the greatest sum along any non-empty path connected through parent-child edges in the tree.
Examples
Example 1
Input
[-8,4,11,null,null,6,12]Output
29Example 2
Input
[2,1,4]Output
7Example 3
Input
[-6,5,12,null,null,4,3]Output
19Approach
Each node returns the best downward path it can extend, ignoring negative branches, and updates the overall best with value + left gain + right gain.
| Pattern | Post-order DFS with a global best |
|---|---|
| Time | O(n) |
| Space | O(h) |
Watch out for
If every value is negative the answer is the largest single node, never 0.