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.
class Solution {
int index;
public TreeNode buildTree(int[] preorder, int[] inorder) {
index = 0;
return build(preorder, inorder, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int[] inorder, int start, int end) {
if (start > end) return null;
TreeNode root = new TreeNode(preorder[index++]);
int i = start;
while (i <= end && inorder[i] != root.val) i++;
root.left = build(preorder, inorder, start, i - 1);
root.right = build(preorder, inorder, i + 1, end);
return root;
}
}Follow-up:
Construct a binary tree from postorder and inorder traversal
