LeetCode - Construct Binary Tree from Preorder and Inorder Traversal
Problem description
Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
For example, given
1
2
3
4
5
6
7
8
9
10
11
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
Analysis
Basic idea is to use a recursion for start and end in inorder array. And if we use preorder recursion, the output will be in preorder. Thus the sequence of the root node value in our recursion would be the same as the preorder array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
HashMap<Integer, Integer> indexes = new HashMap<>();
int pre_index = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i< inorder.length; i++){
indexes.put(inorder[i], i);
}
return build(preorder, inorder, 0, inorder.length - 1);
}
TreeNode build(int[] preorder, int[] inorder, int start, int end){// start and end for inorder array
if (start < 0 || end > inorder.length || start > end){
return null;
}
if (start == end){
return new TreeNode(preorder[pre_index++]);
}
TreeNode root = new TreeNode(preorder[pre_index]);
int startPos = indexes.get(preorder[pre_index]);
pre_index++;
root.left = build(preorder, inorder, start, startPos - 1);
root.right = build(preorder, inorder, startPos + 1, end);
return root;
}
What to improve
- the key point for this is that we need to use the inorder array to separate the tree.