Heaviest Path Anywhere
HardTrees
Problem
A path in a binary tree is a sequence of distinct nodes where each consecutive pair is joined by an edge; it may start and end anywhere and contains at least one node. Its weight is the sum of its values.
Given the root of a non-empty tree, return the maximum weight of any path.
Example 1
- Input:
- root = [-10, 9, 20, null, null, 15, 7]
- Output:
- 42
15 → 20 → 7 weighs 42; including -10 would only hurt.
Example 2
- Input:
- root = [1, 2, 3]
- Output:
- 6
2 → 1 → 3.
Example 3
- Input:
- root = [-3]
- Output:
- -3
A path must contain at least one node.
Constraints
- 1 ≤ number of nodes ≤ 3 · 10^4
- Tree height ≤ 500
- -1000 ≤ node.val ≤ 1000
Hint
Show the first hint
Every path has a single topmost node. What is the best path that has a given node as its top?
Walkthrough
How to approach it
01Clarify before coding
- Must the path go through the root or end at a leaf? Neither.
- Can all values be negative? Yes: the answer is then the largest single value, never 0.
- Can the path use a node twice? No, it is a simple path.
02Brute force
For every pair of nodes, walk the path between them and sum it.
Cost: O(n²) pairs times O(h) per path: hopeless for 3 · 10^4 nodes.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.