Description
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.
Examples
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7][3,9,20,null,null,15,7]Preorder's first element (3) is the root. In inorder, elements left of 3 form left subtree (just 9), elements right form right subtree (15,20,7). Recursively applying this builds the full tree.
preorder = [-1], inorder = [-1][-1]With only one element in both arrays, the tree has just the root node -1.
preorder = [1,2,4,5,3,6], inorder = [4,2,5,1,6,3][1,2,3,4,5,6]The root is 1 (first in preorder). In inorder, elements [4,2,5] are left of root 1, and [6,3] are right. For left subtree: root is 2, with 4 as left child and 5 as right child. For right subtree: root is 3 with 6 as left child. This creates a complete binary tree with all levels filled except the last level.
Constraints
- •
1 ≤ preorder.length ≤ 3000 - •
inorder.length == preorder.length - •
-3000 ≤ preorder[i], inorder[i] ≤ 3000 - •
preorder and inorder consist of unique values.