521. Richest Search Subtree
A museum lays out its rooms as a binary tree, and every room carries a signed visitor score. A catalogue wing is a room together with everything below it, but only if that group obeys the search rule: for every room inside it, all scores in its left part are strictly smaller than the room's score and all scores in its right part are strictly larger.
Given root, return the largest possible sum of the scores in a single catalogue wing. A wing may be a single room, a branch of the tree or the whole tree. If every wing has a negative total, the museum may also choose to open no wing at all, so the answer is never below 0. An empty tree gives 0.
Example 1
- Input:
- root = [12,7,20,3,9,15,31,1,null,8]
- Output:
- 106
- Explanation:
The whole tree obeys the search rule, so its total 12+7+20+3+9+15+31+1+8 = 106 is the largest sum.
Example 2
- Input:
- root = [6,-4,9,-7,-2,8,12,null,null,null,5]
- Output:
- 29
- Explanation:
The whole tree is a valid wing worth 27, but the branch rooted at 9 (keys 8, 9, 12) is also valid and sums to 29, which is larger.
Constraints
0 ≤ number of nodes ≤ 4 * 104
-1000 ≤ node value ≤ 1000 (values may repeat; a repeated value breaks the strict search rule)
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,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)