482. Richest Path
A treasure map shows hidden caches linked together as a binary tree, and each cache carries a score that may be negative. A route is a sequence of one or more nodes in which every two consecutive nodes are joined by a parent-child link, and no node is used twice. A route does not have to start at the root or end at a leaf: it may climb from a node up to some ancestor and then descend into a different branch, but it can never turn back onto a node it has already used.
The wealth of a route is the sum of the scores of its nodes. Given the root of the tree as root, return the largest wealth that any route in the tree can reach. The tree has at least one node, so a route always exists, and the answer fits in a 32-bit signed integer.
Example 1
- Input:
- root = [-4,6,5,null,-2,3,9]
- Output:
- 17
- Explanation:
The best route is 3 - 5 - 9 with wealth 17.
Example 2
- Input:
- root = [-8,-3,-6]
- Output:
- -3
- Explanation:
All scores are negative, so the best route is the single node -3.
Example 3
- Input:
- root = [2,-1,4,7,null,-5,3]
- Output:
- 15
- Explanation:
The route 7, -1, 2, 4, 3 has wealth 15, the best possible.
Constraints
1 ≤ number of nodes ≤ 105
-1000 ≤ Node.val ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)