515. Search Tree From Preorder
A seed bank wrote down the labels of a binary search tree by visiting each node before its subtrees, always finishing the left subtree before the right one. The tree itself was lost, but the list preorder survived.
Rebuild the binary search tree whose pre-order listing is exactly preorder and return its root. All keys are distinct and the list is guaranteed to come from some search tree, so the tree is uniquely determined. The result is compared through its level-order listing.
Example 1
- Input:
- preorder = [20,10,5,15,30,25,35]
- Output:
- [20,10,30,5,15,25,35]
- Explanation:
The first key 20 is the root; 10, 5, 15 are smaller and form its left subtree, and 30, 25, 35 form its right subtree: [20,10,30,5,15,25,35].
Example 2
- Input:
- preorder = [7,9,12]
- Output:
- [7,null,9,null,12]
- Explanation:
Each key is larger than the previous one, so every node is the right child of the one before it.
Constraints
1 ≤ preorder.length ≤ 1000
-104 ≤ preorder[i] ≤ 104
All values are distinct and preorder is the pre-order listing of a valid binary search tree.
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)