Description
Given an array of integers preorder, which represents the preorder traversal of a BST, construct the tree and return its root.
Examples
Input:
preorder = [8,5,1,7,10,12]Output:
[8,5,10,1,7,null,12]Explanation:
Reconstructed BST from preorder.
Input:
preorder = [15,10,5,12,20,18,25]Output:
[15,10,20,5,12,18,25]Explanation:
The root is 15. Values less than 15 (10,5,12) form the left subtree, values greater than 15 (20,18,25) form the right subtree. In the left subtree: 10 is root with 5 as left child and 12 as right child. In the right subtree: 20 is root with 18 as left child and 25 as right child.
Input:
preorder = [50,30,25,40,35,45]Output:
[50,30,null,25,40,null,null,null,35,45]Explanation:
The root is 50. All values (30,25,40,35,45) are less than 50, so there's no right subtree of the root. The left subtree has 30 as root, 25 as left child of 30, and 40 as right child of 30. Under 40, there are 35 as left child and 45 as right child, following the BST property.
Constraints
- •
1 ≤ preorder.length ≤ 100 - •
1 ≤ preorder[i] ≤ 10⁸ - •
All values are unique.