hardTreesPure DSA~40 min
Max Value Path In Org Tree
Each node in a binary org tree carries a signed impact score (a reorg can be negative). A 'path' is any chain of connected nodes, not necessarily through the root. Find the maximum total impact of any path.
Problem
Given the root of a binary tree where each node has an integer value, return the maximum path sum. A path is a sequence of nodes connected by edges, each node appearing once, and need not pass through the root.
Input
The root of a binary tree with 1 ≤ n ≤ 3·10^4 nodes, −1000 ≤ value ≤ 1000.
Output
An integer: the maximum path sum.
Constraints
- 1 ≤ number of nodes ≤ 3·10^4
- Node values may be negative
- A path bends at most once (it goes up to a peak then down)
Examples
Example 1
Input
tree = [1,2,3]
Output
6
Path 2 -> 1 -> 3 sums to 6.
Example 2
Input
tree = [-10,9,20,null,null,15,7]
Output
42
Path 15 -> 20 -> 7 sums to 42; the negative root is skipped.