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
Input:
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]Output:
[3,9,20,null,null,15,7]Explanation:
Construct tree from the traversals.
Input:
preorder = [-1], inorder = [-1]Output:
[-1]Explanation:
Single node tree.
Input:
preorder = [1,2,4,5,3,6], inorder = [4,2,5,1,6,3]Output:
[1,2,3,4,5,6]Explanation:
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.