/106. Construct Binary Tree from Inorder and Postorder Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

Medium
Arrays68.2% acceptance

Given two integer arrays representing the inorder and postorder traversals of a binary tree, reconstruct the binary tree and return its level-order traversal as a list, where null values represent missing children.

Example 1

Input: inorder = [2,1,4,3,5], postorder = [2,4,5,3,1]

Output: [1,2,3,null,null,4,5]

Explanation: The reconstructed tree is: 1 as root, 2 as left child, 3 as right child, 4 as left child of 3, 5 as right child of 3.

Example 2

Input: inorder = [10], postorder = [10]

Output: [10]

Explanation: Single node tree.

Constraints

  • 1 <= len(inorder) <= 3000
  • len(postorder) == len(inorder)
  • -3000 <= inorder[i], postorder[i] <= 3000
  • All values in inorder and postorder are unique
  • Each value in postorder appears in inorder
  • inorder is the inorder traversal of the tree
  • postorder is the postorder traversal of the tree
Python (current runtime)

Case 1

Input: inorder = [6,2,7,1,5,3,4], postorder = [6,7,2,5,4,3,1]

Expected: [1,2,3,6,7,5,4]

Case 2

Input: inorder = [8,6,9], postorder = [8,9,6]

Expected: [6,8,9]

Case 3

Input: inorder = [11,12,13], postorder = [11,13,12]

Expected: [12,11,13]