noodleProblems/
Construct Binary Tree from Preorder and Inorder Traversal
#134

Construct Binary Tree from Preorder and Inorder Traversal

AlgorithmmediumArrayHash TableDivide And ConquerTreeBinary Tree

Given two integer arrays preorder and inorder — the preorder and inorder traversals of the *same* binary tree, with all values **distinct** — reconstruct and return the tree.

In preorder, the first element is always the **root**. In inorder, everything left of the root belongs to the left subtree and everything right of it to the right subtree. Recurse on each side.

The reconstructed tree is returned as a level-order array where null marks a missing child.

Example cases

  • classic
    in preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
    out [3,9,20,null,null,15,7]9315207
    3 is the root; 9 is left of it inorder (left subtree), 15/20/7 are right.
  • two nodes
    in preorder = [1,2], inorder = [2,1]
    out [1,2]21
  • single
    in preorder = [-1], inorder = [-1]
    out [-1]-1

Constraints

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder and inorder consist of unique values; inorder is a permutation of preorder.
Saved
preorder =
[3,9,20,15,7]
inorder =
[9,3,15,20,7]