Construct Binary Tree from Preorder and Inorder
Given preorder and inorder traversal of a tree, construct the binary tree.
Constraints:
- 1 <= preorder.length <= 100
- 1 <= inorder.length <= 100
- -100 <= preorder[i] <= 100
- -100 <= inorder[i] <= 100
- preorder and inorder represent a valid binary tree
Examples:
Input: [3,9,20,15,7] and [9,3,15,20,7]
Output: a binary tree where 3 is the root, 9 is the left child, and 20 is the right child. 15 and 7 are the left and right children of 20 respectively
Explanation: The preorder traversal visits the root first, then the left subtree, and finally the right subtree. The inorder traversal visits the left subtree, then the root, and finally the right subtree. By combining these two traversals, we can construct the binary tree.
Solutions
Recursive Approach
The recursive approach works by selecting the root node from the preorder traversal, finding its position in the inorder traversal, and then recursively constructing the left and right subtrees.
function buildTree(preorder, inorder) {
let index = 0;
function build(preorder, inorder) {
if (inorder.length === 0) return null;
let root = new TreeNode(preorder[index++]);
let i = inorder.indexOf(root.val);
root.left = build(preorder, inorder.slice(0, i));
root.right = build(preorder, inorder.slice(i + 1));
return root;
}
return build(preorder, inorder);
}
Follow-up:
Construct a binary tree from postorder and inorder traversal
