Construct BT from Inorder and Postorder

Construct Binary Tree from Inorder and Postorder Traversal

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Examples

Example 1:

Input: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]
Output: [3, 9, 20, null, null, 15, 7]

      3
     / \
    9  20
       / \
      15   7

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

Constraints

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder and postorder consist of unique values.

Expected Complexity

• Time: O(n)
• Space: O(n)