Construct Binary Tree from Preorder and Inorder

You are given the preorder (node, left, right) and inorder (left, node, right) traversals of a binary tree with distinct values. Rebuild the tree and print it in level order.

Input:

• line 1: n — the number of nodes
• line 2: the preorder sequence
• line 3: the inorder sequence

Output: the tree in level order (top to bottom, left to right) with null for a missing child, trailing nulls left out — e.g. 3 9 20 null null 15 7.

Constraints: 1 ≤ n ≤ 10⁴, distinct values between −10⁴ and 10⁴. The tree's height is at most 500.

Think about it: the first preorder value is the root. Its position in the inorder sequence splits the rest into left and right subtrees. A hash map from value → inorder index makes each split O(1), so the whole build is O(n).