Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
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
Solution:
Same approach with Construct Binary Tree from Preorder and Inorder Traversal.
Code:
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildTree(inorder, 0, inorder.length - 1,
postorder, 0, postorder.length - 1);
}
private TreeNode buildTree(int[] inorder, int istart, int iend,
int[] postorder, int pstart, int pend) {
if (istart > iend) {
return null;
}
int val = postorder[pend];
int idx = findInorder(inorder, istart, iend, val);
TreeNode node = new TreeNode(val);
int rightTreeSize = iend - idx;
node.left = buildTree(inorder, istart, idx - 1,
postorder, pstart, pend - rightTreeSize - 1);
node.right = buildTree(inorder, idx + 1, iend,
postorder, pend - rightTreeSize, pend - 1);
return node;
}
private int findInorder(int[] inorder, int istart, int iend, int val) {
for (; istart <= iend; istart++) {
if (inorder[istart] == val) {
return istart;
}
}
return -1;
}
}