Facebook PixelConstruct Binary Tree from Preorder and Inorder Traversal — Coding Practice
Construct Binary Tree from Preorder and Inorder TraversalMedium

Construct Binary Tree from Preorder and Inorder Traversal

Medium 13.4k64% acceptance
ArrayHash TableDivide and ConquerTreeBinary Tree

Given two integer arrays preorder and inorder that record the preorder and inorder traversals of the same binary tree, rebuild the tree and return its root.

You may assume all values are distinct. Return the reconstructed tree; it will be compared by its level-order array form.

Both inputs are plain number arrays.

Example 1
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Preorder gives the root 3 first; inorder splits the remaining values into the left subtree {9} and right subtree {15,20,7}.
Example 2
Input: preorder = [-1], inorder = [-1]
Output: [-1]
Example 3
Input: preorder = [1,2], inorder = [2,1]
Output: [1,2]
2 appears before 1 in inorder, so 2 is the left child of root 1.
Constraints
  • 1 ≤ preorder.length ≤ 3000
  • inorder.length == preorder.length
  • All values are distinct and the two arrays describe the same tree.
Asked atAmazonMicrosoftMetaBloomberg
JavaScript
Loading editor…
Case 1
[3,9,20,15,7], [9,3,15,20,7]
expected: [3,9,20,null,null,15,7]
Case 2
[-1], [-1]
expected: [-1]
Case 3
[1,2], [2,1]
expected: [1,2]
Case 4
[1,2], [1,2]
expected: [1,null,2]
Case 5
[3,1,2,4], [1,3,2,4]
expected: [3,1,2,null,null,null,4]
Case 6
[1,2,3,4,5], [3,2,4,1,5]
expected: [1,2,5,3,4]