FastPrepConstruct a Tree from Level-Order and Inorder Traversals

Construct a Tree from Level-Order and Inorder Traversals

Salesforce logoSalesforce● HardFULLTIMEONSITE INTERVIEW
Learn

Problem statement

Given the levelOrder and inorder traversals of the same binary tree, reconstruct and return its root.

All node values are distinct. Both arrays contain the same values, and together they describe exactly one valid binary tree.

Function

buildTree(levelOrder: int[], inorder: int[]) → TreeNode

Examples

Example 1

levelOrder = [3,9,20,15,7]inorder = [9,3,15,20,7]return = [3,9,20,null,null,15,7]

The root 3 appears first in level order; the inorder split places 9 left and the remaining nodes right.

Example 2

levelOrder = [1]inorder = [1]return = [1]

Both traversals describe a one-node tree.

Example 3

levelOrder = [1,2,3,4,5]inorder = [4,2,5,1,3]return = [1,2,3,4,5]

The traversals reconstruct the shown complete upper levels.

Constraints

  • 1 <= levelOrder.length == inorder.length <= 1200.
  • -10^9 <= levelOrder[i], inorder[i] <= 10^9.
  • Each traversal contains distinct values, and both contain the same set of values.
  • The arrays are valid traversals of one binary tree.

More Salesforce problems

See Salesforce hiring insights
public TreeNode buildTree(int[] levelOrder, int[] inorder) {
  // write your code here
}
levelOrder[3,9,20,15,7]
inorder[9,3,15,20,7]
expected[3,9,20,null,null,15,7]
Checking account…