Given two lists of distinct integers, preorder and inorder, that are the preorder and inorder traversals of the same binary tree, rebuild that tree and return its root.
Examples
3
/ \
9 20
/ \
15 7
Input: preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
Output: tree_to_list(...) == [3, 9, 20, None, None, 15, 7]
Input: preorder = [1, 2], inorder = [2, 1]
Output: [1, 2]
Constraints
0 <= len(preorder) == len(inorder) <= 1000- All values are distinct and the two lists describe a valid tree
Goals
- Use the preorder sequence to pick each root and the inorder sequence to split its subtrees
- Avoid O(n^2) slicing with an index map and boundaries