Given preorder, the preorder traversal of a binary search tree with distinct values (every node's left subtree holds smaller values and its right subtree larger values), rebuild the tree and return its root.
Examples
8
/ \
5 10
/ \ \
1 7 12
Input: preorder = [8, 5, 1, 7, 10, 12]
Output: tree_to_list(...) == [8, 5, 10, 1, 7, None, 12]
Input: preorder = [3, 1, 2]
Output: [3, 1, None, None, 2]
Constraints
0 <= len(preorder) <= 1000- All values are distinct
Goals
- Use BST ordering instead of a second traversal to decide where each value goes
- Carry an upper bound through the recursion so each value is consumed once