Construct Binary Tree from Inorder and Postorder traversal

07/11/2016 Tree Array Depth First Search

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.


Solution

Result: Accepted Time: 16 ms

Here should be some explanations.

struct TreeNode * build(int * in,int *post,int left,int right,int *ptr)
{
    if(left >= right || *ptr < 0)
        return NULL;
    int mid = left;
    while(post[*ptr] != in[mid]) mid++;
    struct TreeNode * root = malloc(sizeof(struct TreeNode));
    root->val = post[(*ptr)--];
    root->right = build(in,post,mid+1,right,ptr);
    root->left = build(in,post,left,mid,ptr);
    return root;
}
struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
    int ptr = inorderSize-1;
    return build(inorder,postorder,0,postorderSize,&ptr);
}

Complexity Analytics

  • Time Complexity:
  • Space Complexity: