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;
}

results matching ""

    No results matching ""