Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Notice
You may assume that duplicates do not exist in the tree.
Example
Given inorder [1,2,3] and postorder [1,3,2], return a tree:
2
/ \
1 3
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length != postorder.length) {
return null;
}
return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
public TreeNode buildTree(int[] in, int istart, int iend, int[] post, int pstart, int pend) {
if(istart > iend || pstart > pend) {
return null;
}
TreeNode root = new TreeNode(post[pend]);
int pos = 0;
for(int i = 0; i < in.length; i++) {
if(in[i] == root.val) {
pos = i;
}
}
int len = iend - pos;
root.left = buildTree(in, istart, pos - 1, post, pstart, pend - 1 - len);
root.right = buildTree(in, pos + 1, iend, post, pend - len, pend - 1);
return root;
}