Given two integer arrays, preorder_sequence and inorder_sequence, representing the preorder and inorder traversals of a binary tree with unique values, reconstruct the binary tree and return its root node. The output should be the tree serialized in level-order as a list, where null represents missing children.
Example 1
Input: preorder_sequence = [10,5,1,7,15,12,20] inorder_sequence = [1,5,7,10,12,15,20]
Output: [10,5,15,1,7,12,20]
Explanation: The tree is constructed as: 10 / \ 5 15 / \ / \ 1 7 12 20
Example 2
Input: preorder_sequence = [2,1,3] inorder_sequence = [1,2,3]
Output: [2,1,3]
Explanation: The tree is: 2 / \ 1 3
Example 3
Input: preorder_sequence = [8] inorder_sequence = [8]
Output: [8]
Explanation: Single node tree.
Constraints
Case 1
Input: preorder_sequence = [4,2,1,3,6,5,7] inorder_sequence = [1,2,3,4,5,6,7]
Expected: [4,2,6,1,3,5,7]
Case 2
Input: preorder_sequence = [100,50,25,75,150,125,175] inorder_sequence = [25,50,75,100,125,150,175]
Expected: [100,50,150,25,75,125,175]
Case 3
Input: preorder_sequence = [5,3,2,4,8,7,9] inorder_sequence = [2,3,4,5,7,8,9]
Expected: [5,3,8,2,4,7,9]
Case 4
Input: preorder_sequence = [1] inorder_sequence = [1]
Expected: [1]
Case 5
Input: preorder_sequence = [6,2,1,4,3,5,8,7,9] inorder_sequence = [1,2,3,4,5,6,7,8,9]
Expected: [6,2,8,1,4,7,9,None,None,3,5]