Best Path Sum in a Tree
A binary tree is given as a level-order array tree with null for missing children. A path is any sequence of nodes where each pair of neighbours is connected by an edge, and no node appears twice. A path has at least one node and does not have to pass through the root.
Return the largest possible sum of node values on a path. Values can be negative.
Example 1
Input: tree = [1,2,3] Output: 6 Explanation: 2 -> 1 -> 3.
Example 2
Input: tree = [-10,9,20,null,null,15,7] Output: 42 Explanation: 15 -> 20 -> 7.
Constraints
- 1 <= number of nodes <= 3 * 10^4
- -1000 <= node value <= 1000
Hint 1
For each node compute the best downward path that starts at it: its value plus the better non-negative child gain.
Hint 2
A path that bends at a node uses both child gains; track the best of those across all nodes.
Discussion 0
Join free to post in the discussion.
Good practice for: Backend Developer, Game Developer, Data Scientist, Full Stack Developer, AI Engineer (LLM & Generative AI)
Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.