[LeetCode 106] Construct Binary Tree from Inorder and Postorder

Question

link

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Stats

Frequency	3
Difficulty	3
Adjusted Difficulty	3
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is exactly the same question as “Construct Binary Tree from Preorder and Inorder”.

Solution

I post the code from this article.

Code

public TreeNode buildTree(int[] inorder, int[] postorder) {
    int inStart = 0, inEnd = inorder.length-1;
    int postStart =0, postEnd = postorder.length-1;
    return buildTree(inorder, inStart, inEnd, postorder, postStart, postEnd);
}

public TreeNode buildTree(int[] inorder, int inStart, int inEnd,
                          int[] postorder, int postStart, int postEnd){
    if(inStart > inEnd || postStart > postEnd)
        return null;
    int rootValue = postorder[postEnd];
    TreeNode root = new TreeNode(rootValue);
    int k=0;
    for(int i=0; i< inorder.length; i++){
        if(inorder[i]==rootValue){
            k = i;
            break;
        }
    }
    root.left = buildTree(inorder, inStart, k-1,
        postorder, postStart, postStart+k-(inStart+1));
    root.right = buildTree(inorder, k+1, inEnd,
        postorder, postStart+k-inStart, postEnd-1);
    return root;
}