LeetCode - Construct Binary Tree from Inorder and Postorder Traversal
Problem description
Given inorder and postorder 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
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
Analysis
Basically, we can use the inorder array to separate the tree, one tricky point is that you need to use the last of the postorder array to find the root. And then in post order traversal, if you start from the end, then the order would be root, right, left.
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int post_index;
HashMap<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
post_index = inorder.length - 1;
for (int i = 0; i < inorder.length; i++){
map.put(inorder[i], i);
}
return build(inorder, postorder, 0, inorder.length - 1);
}
TreeNode build(int[] inorder, int[] postorder, int start, int end){
if (start < 0 || end >= inorder.length || start > end){
return null;
}
if (start == end){
return new TreeNode(postorder[post_index--]);
}
TreeNode root = new TreeNode(postorder[post_index]);
int root_index = map.get(postorder[post_index]);
post_index--;
root.right = build(inorder, postorder, root_index+1, end);
root.left = build(inorder, postorder, start, root_index - 1);
return root;
}
}