Construct Binary Tree from Preorder and Inorder Traversal
MediumTrees
You are given two integer arrays describing the same binary tree, in which all values are distinct:
preorderlists the values in preorder (node, then left subtree, then right subtree).inorderlists the values in inorder (left subtree, then node, then right subtree).
Rebuild the tree and return its root. Because values are distinct, exactly one tree matches both traversals. The returned tree is checked in level order, written with null for missing children and no trailing nulls.
Example 1
- Input:
- preorder = [8, 4, 2, 6, 10, 9, 12], inorder = [2, 4, 6, 8, 9, 10, 12]
- Output:
- [8,4,10,2,6,9,12]
- Explanation
- Preorder starts with 8, so 8 is the root. In inorder, 2, 4, 6 sit left of 8 and 9, 10, 12 sit right of it. Repeating the split on each side gives 4 over 2 and 6, and 10 over 9 and 12.
Example 2
- Input:
- preorder = [1, 2, 4, 3, 5], inorder = [4, 2, 1, 5, 3]
- Output:
- [1,2,3,4,null,5]
- Explanation
- Root 1 splits inorder into
[4, 2]and[5, 3]. On the left, preorder says 2 comes first, so 2 is the subtree root with 4 as its left child; on the right, 3 is the root with 5 as its left child.
Example 3
- Input:
- preorder = [3, 1, 2], inorder = [1, 2, 3]
- Output:
- [3,1,null,null,2]
- Explanation
- Root 3 has everything to its left in inorder, so it has no right child. Inside the left part, preorder makes 1 the root, and 2 comes after 1 in inorder, so 2 is 1's right child.
Constraints
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000- All values are distinct, and
inordercontains exactly the values ofpreorder - The input always describes a valid tree, whose height is at most
500