897. Construct Binary Tree from Postorder and Inorder

Given the postorder 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 ' | ' (postorder first, then inorder).

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

Output: Array — the reconstructed tree in level order.

Examples

Input: [9,15,7,20,3] | [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: [2,1] | [1,2]
Output: [1,null,2]
Explanation: 2 is a right child.

Constraints

• 1<=nodes<=3000
• values distinct

Asked by