520. Largest Search Subtree
An orchard map is a binary tree of numbered plots. Some of its sub-branches happen to be ordered like a search tree: for a plot with key k, every key on the left of it is strictly smaller than k and every key on the right is strictly larger, and the same holds inside every plot of that sub-branch.
Given the tree root, which is not necessarily a search tree itself, find the sub-branch (a node together with all its descendants) that is a valid search tree and contains the most nodes. Return that node count. A single node counts as a search tree of size 1, and an empty tree gives 0.
Example 1
- Input:
- root = [9,4,12,2,6,11,3]
- Output:
- 3
- Explanation:
The node 12 has a left child 11 and a right child 3 which is smaller than 12, so it is not a search tree; the subtree rooted at 4 with children 2 and 6 has 3 nodes and is the largest.
Example 2
- Input:
- root = [8,3,10,1,6,null,14]
- Output:
- 6
- Explanation:
The whole tree is a valid search tree, so all 6 nodes count.
Constraints
0 ≤ number of nodes ≤ 105
-104 ≤ node key ≤ 104; keys may repeat
A search tree needs strictly smaller keys on the left and strictly larger keys on the right.
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 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)