524. Preorder Could Be a Search Tree
A surveyor walked through a forest of numbered stations and jotted down the visiting order preorder: each station was written down first, then everything in its left part, then everything in its right part. The map itself was lost.
Decide whether these notes could have come from a binary search tree, that is, a binary tree in which every station's left part holds only strictly smaller numbers and its right part holds only strictly larger ones. Return true if some binary search tree has exactly this preorder, otherwise false. A single number is always valid.
Example 1
- Input:
- preorder = [8,5,1,7,10,12]
- Output:
- true
- Explanation:
Root 8, then 5 with left child 1 and right child 7, then 10 with right child 12 gives a valid search tree with this preorder.
Example 2
- Input:
- preorder = [9,4,2,7,12,6]
- Output:
- false
- Explanation:
After 12 the walk is inside the right subtree of 9, so a later value 6 (smaller than 9) makes the notes impossible.
Constraints
1 ≤ preorder.length ≤ 105
-109 ≤ preorder[i] ≤ 109
All values are distinct
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(n)