Given two integer arrays preorder and inorder, the preorder and inorder traversals of the same binary tree, build the tree and return its root.
Trees are written level by level, with null for a missing child. Every value in the tree is unique.
Examples
Example 1
- Input
- preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
- Output
- [3, 9, 20, null, null, 15, 7]
Example 2
- Input
- preorder = [-1], inorder = [-1]
- Output
- [-1]
Constraints
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000- Values are unique, and both arrays describe the same tree.