Tree From Pre/Inorder Traversals

Given a list of unique integers preorder and another list of unique integers inorder, representing the pre-order and in-order traversals of a binary tree, reconstruct the tree and return the root.

Constraints

• n ≤ 100,000 where n is the length of preorder and inorder

https://binarysearch.com/problems/Tree-From-PreInorder-Traversals

Examples

Example 1

Input

• preorder = [4, 2, 1, 0, 3]
• inorder = [2, 1, 0, 3, 4]

Output

• answer =

Solution