896. Construct Binary Tree from Preorder and Inorder

Given the preorder and inorder traversals of a binary tree with distinct values, reconstruct the tree and return it as a level-order array with null for missing children. The two traversals are given as JSON arrays separated by ' | ' (preorder first, then inorder).

Input: Two JSON arrays (preorder | inorder), separated by ' | '.

Output: Array — the reconstructed tree in level order.

Examples

Input: [3,9,20,15,7] | [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Explanation: Standard reconstruction.

Input: [1] | [1]
Output: [1]
Explanation: Single node.

Input: [1,2] | [2,1]
Output: [1,2]
Explanation: 2 is a left child.

Constraints

• 1<=nodes<=3000
• values distinct

Asked by