Construct Binary Tree from Preorder and Inorder Traversal
Medium
Array
Hash Table
Divide and Conquer
Tree
Binary Tree
Given two integer arrays `preorder` and `inorder` where `preorder` is the preorder traversal of a binary tree and `inorder` is the inorder traversal of the same tree, construct and return *the binary tree*.
Example 1
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Example 2
Input: preorder = [-1], inorder = [-1]
Output: [-1]
Example 3
Input: preorder = [1,2,3], inorder = [2,1,3]
Output: [1,2,3]

Constraints

  • •1 <= preorder.length <= 3000
  • •inorder.length == preorder.length
  • •-3000 <= preorder[i], inorder[i] <= 3000
  • •preorder and inorder consist of unique values.
  • •Each value of inorder also appears in preorder.
  • •preorder is guaranteed to be the preorder traversal of the tree.
  • •inorder is guaranteed to be the inorder traversal of the tree.
Time Complexity
O(n)
Space Complexity
O(n)
14
Case 1
Input: [3,9,20,15,7] [9,3,15,20,7]
Expected: [3,9,20,null,null,15,7]
Case 2
Input: [-1] [-1]
Expected: [-1]
Case 3
Input: [1,2,3] [2,1,3]
Expected: [1,2,3]