Construct Binary Tree from Preorder and Inorder Traversals

Given the preorder and inorder traversals of a binary tree, construct the binary tree.

Recall that the preorder traversal follows the order: $$\text{Preorder: root, left, right}$$ and the inorder traversal follows the order: $$\text{Inorder: left, root, right}$$.

Once the tree is constructed, output its level order traversal in Python list format. For missing (null) nodes, output None. Trailing None values should be omitted.

inputFormat

The input is given as follows via standard input (stdin):

1. The first line contains an integer (n), representing the number of nodes in the tree.
   
2. The second line contains (n) space-separated integers representing the preorder traversal.
   
3. The third line contains (n) space-separated integers representing the inorder traversal.
   
   For an empty tree, (n = 0) and the following two lines will be empty.

outputFormat

Output a single line to standard output (stdout) containing the level order traversal of the constructed binary tree in Python list format. For example: [3, 9, 20, None, None, 15, 7].## sample

5
3 9 20 15 7
9 3 15 20 7

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