#1008
Construct Binary Search Tree from Preorder Traversal
pupil · 395 · lc medium +24 · failed · 84.1% accepted · 6,744 likes · top 95%
Description
Given an array of integers preorder representing the preorder traversal of a BST, reconstruct the BST and return its root.
It is guaranteed that a valid BST always exists for the given input.
In a BST, every descendant of Node.left is strictly less than Node.val, and every descendant of Node.right is strictly greater than Node.val.
A preorder traversal visits the current node before traversing its left and right subtrees.
Example 1:
Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
Example 2:
Input: preorder = [1,3]
Output: [1,null,3]
Code
1
2
3
4
5
6
7
8
9