Construct Binary Tree from Inorder and Postorder Traversal

Question

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

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

Answer 1

The following solution uses very similar approach to solve Construct Binary Tree from Preorder and Inorder Traversal.

Below is the code:

const int MAX = 256;
// a fast lookup for inorder's element -> index
// binary tree's element must be in the range of [0, MAX-1]
int mapIndex[MAX];
void mapToIndices(int inorder[], int n) {
    for (int i = 0; i < n; i++) {
        assert(0 <= inorder[i] && inorder[i] <= MAX-1);
        mapIndex[inorder[i]] = i;
    }
}

// precondition: mapToIndices must be called before entry
Node *buildInorderPostorder(int in[], int post[], int n, int offset) {
    assert(n >= 0);
    if (n == 0) return NULL;
    int rootVal = post[n-1];
    int i = mapIndex[rootVal]-offset;  // the divider's index
    Node *root = new Node(rootVal);
    root->left = buildInorderPostorder(in, post, i, offset);
    root->right = buildInorderPostorder(in+i+1, post+i, n-i-1, offset+i+1);
    return root;
}

Answer 2

/ * Definition for binary tree * struct TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public:

TreeNode *contree(vector<int> &inorder,vector<int> &postorder, int ls, int le,int ps, int pe){

    if (ls>le) {return NULL;}
    if (ps>pe) {return NULL;}

    int i=ls;
    for (;i<=le;i++){
        if (inorder[i]==postorder[pe]) {break;}
    }

    TreeNode* root = new TreeNode(postorder[pe]);
    root->left = contree(inorder,postorder,ls,i-1,ps,ps+i-ls-1);        
    root->right = contree(inorder,postorder,i+1,le,pe-(le-i),pe-1);

    return root;
}
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if (postorder.empty()) {return NULL;}
    return contree(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1);
}

};

Answer 3

Provide a solution using Java.

public TreeNode buildTree(int[] inorder, int[] postorder) {
    if (inorder.length == 0)
        return null;
    if (inorder.length == 1)
        return new TreeNode(inorder[0]);

    // the last item in postorder is root
    TreeNode root = new TreeNode(postorder[postorder.length - 1]);

    int i = inorder.length - 1;
    for (; inorder[i] != root.val; i--)
        ;

    // inorder.length == postorder.length
    if (i < inorder.length - 1) {
        root.right = buildTree(
                Arrays.copyOfRange(inorder, i + 1, inorder.length),
                Arrays.copyOfRange(postorder, i, postorder.length - 1));            
    }
    if (i > 0) {
        root.left = buildTree(Arrays.copyOfRange(inorder, 0, i),
                Arrays.copyOfRange(postorder, 0, i));
    }

    return root;
}

Answer 4

public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder.length == 0)
            return null;
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        int rootIndexOfInorder = 0;
        while(inorder[rootIndexOfInorder] != postorder[postorder.length - 1])   rootIndexOfInorder++;
        root.left = buildTree(Arrays.copyOf(inorder, rootIndexOfInorder), Arrays.copyOf(postorder, rootIndexOfInorder));
        root.right = buildTree(Arrays.copyOfRange(inorder, rootIndexOfInorder + 1, inorder.length), 
                Arrays.copyOfRange(postorder, rootIndexOfInorder, postorder.length - 1));
        return root;
    }

Answer 5

TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if (inorder.size() != postorder.size())
        return NULL;

    return generateTree(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);

}

TreeNode *generateTree(vector<int> &inorder, vector<int> &postorder, int inLow, int inHigh, int poLow, int poHigh) {

    if(inLow > inHigh || poLow > poHigh)
        return NULL;

    int rootVal = postorder[poHigh];
    TreeNode *root = new TreeNode(rootVal);
    int sep = find(inorder, rootVal, inLow, inHigh);
    if (sep != -1) {
        root->left = generateTree(inorder, postorder, inLow, sep-1, poLow, poLow+(sep-1-inLow));
        root->right = generateTree(inorder, postorder, sep+1, inHigh, poLow+sep-inLow, poHigh-1);
    }
    return root;
}

int find(vector<int> &vec, int value, int low, int high) {
    for(int i=low; i<=high; i++) {
        if (vec[i] == value)
            return i;
    }
    return -1;
}

Answer 6

Parse postorder array from the tail to head. Each node from postorder array separates inorder into two segments: left subtree and right subtree. Recursively build tree by this method.

std::unordered_map<int,int> index_map;

void buildMap(vector<int> &inorder) {
    index_map.clear();
    for (int i = 0; i < inorder.size(); i++) {
        index_map[inorder[i]] = i;
    }
}

TreeNode *buildTreeInOrder(vector<int> &postorder, int post_offset,
        vector<int> &inorder, int in_offset, int len) {
    if (!len)
        return NULL;

    TreeNode *root = new TreeNode(postorder[post_offset]);
    int i = index_map[postorder[post_offset]];

    root->right = buildTreeInOrder(postorder,
            post_offset-1, inorder, in_offset, in_offset-i);
    root->left = buildTreeInOrder(postorder,
            post_offset-(in_offset-i)-1, inorder, in_offset-(in_offset-i)-1, len-(in_offset-i)-1);

    return root;
}

TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if (postorder.size() == 0 && inorder.size() == 0) {
        return NULL;
    }

    buildMap(inorder);
    return buildTreeInOrder(postorder, postorder.size()-1, inorder, inorder.size()-1, postorder.size());
}

Answer 7

1)the last node in postorder is the tree root;

2)find the root node in inorder, then get the left and right subtree order(both postorder and inorder list);

3)if can't find the root node in inorder, then the input is error, can not build the tree;

TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(postorder.empty()) {
        return NULL;
    }
    TreeNode* root = NULL;
    if (!buildSubTree(root, postorder, 0, postorder.size(), inorder, 0, inorder.size())) {
        return NULL;
    }
    return root;
}

bool buildSubTree(TreeNode* &root, vector<int> &postorder, int postbegin, int postend, 
        vector<int> &inorder, int inbegin, int inend) {
    if (postbegin >= postend || inbegin >= inend) {
        return true;
    } else if (postend-postbegin != inend-inbegin) {
        return false;
    }
    root = new TreeNode(postorder[postend-1]);

    int root_index = inbegin;
    for (; root_index < inend; ++root_index) {
        if (inorder[root_index] == root->val) {
            break;
        }
    }
    if (root_index == inend) {
        //error 
        return false;
    }
    if (!buildSubTree(root->left, postorder, postbegin, postbegin+root_index-inbegin,
            inorder, inbegin, root_index)) {
        return false;
    }
    if (!buildSubTree(root->right, postorder, postbegin+root_index-inbegin, postend-1, 
            inorder, root_index+1, inend)) {
        return false;
    }
    return true;
}

Construct Binary Tree from Inorder and Postorder Traversal

Follow this question

Welcome to LeetCode

Related questions