Build a Tree From Preorder and Inorder

You are given the preorder and the inorder traversal of a binary tree with different values. Rebuild the tree and return its root.

The tests write a tree as a level-order list (row by row, left to right) with None for a missing child: [3, 9, 20, None, None, 15, 7] is a root 3 with children 9 and 20, where 20 has children 15 and 7.

For preorder = [3, 9, 20, 15, 7] and inorder = [9, 3, 15, 20, 7] the answer is [3, 9, 20, None, None, 15, 7].

Examples

Example 1

Input:

build_tree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])

Output:

[3, 9, 20, None, None, 15, 7]

Example 2

Input:

build_tree([1], [1])

Output:

[1]

Constraints

• 0 <= number of nodes <= 20000
• The tree is not deeper than 800 levels.
• All values are different.