AlgoLounge

Construct Binary Tree from Preorder and Inorder Traversal

medium

Leetcode 105. Construct Binary Tree From Preorder And Inorder Traversal

You are given two integer arrays `preorder` and `inorder`.

* `preorder` is the preorder traversal of a binary tree

* `inorder` is the inorder traversal of the same tree

* Both arrays are of the same size and consist of unique values.

Rebuild the binary tree from the preorder and inorder traversals and return its root.

Examples

Example 1

Input:  preorder = [1], inorder = [1]
Output: [1]

Constraints

  • `1 <= inorder.length <= 1000`.
  • `inorder.length == preorder.length`
  • `-1000 <= preorder[i], inorder[i] <= 1000`

How the tests work: the tree you return is read back as a level-order array — [3,9,20,null,null,15,7].

TypeScript
Loading editor…
List of test cases (10)
Case 1
preorder = [1]
inorder = [1]
Case 2
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Case 3
preorder = [1,2]
inorder = [2,1]
Case 4
preorder = [1,2,3]
inorder = [2,1,3]
Case 5
preorder = [1,2,4,5,3,6]
inorder = [4,2,5,1,6,3]
Case 6
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Case 7
preorder = [1,2,4,3,5,6]
inorder = [4,2,1,5,3,6]
Case 8
preorder = [5,3,2,4,7,6,8]
inorder = [2,3,4,5,6,7,8]
Case 9
preorder = [10,5,1,7,15,12,20]
inorder = [1,5,7,10,12,15,20]
Case 10
preorder = [8,4,2,1,3,6,5,7]
inorder = [1,2,3,4,5,6,7,8]