Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.2 kB
3
Indexable
Never
#include <stdio.h>
#include <stdlib.h>
 
struct Node
{
    long long int key;
    struct Node *left, *right;
};
 
struct Node* newNode(long long int key);
void preorder(struct Node* root);
struct Node* constructBST(long long int postorder[], long long int start, long long int end);

int show;

 
int main(void)
{
    long long int postorder[200005];
    long long int i=0;
    while( ~scanf("%lld",&postorder[i]) )
    {
        i++;
    }
    long long int n = i++;

    struct Node* root = constructBST(postorder, 0, n - 1);

    preorder(root);
    printf("\n");
 
    return 0;
}

struct Node* newNode(long long int key)
{
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->key = key;
    node->left = node->right = NULL;
 
    return node;
}
 
void preorder(struct Node* root)
{
    if (root == NULL) {
        return;
    }

    if(show)
    {
        printf(" %lld", root->key);
        preorder(root->left);
        preorder(root->right);
    }
    else
    {
        show++;
        printf("%lld", root->key);
        preorder(root->left);
        preorder(root->right);
    }
}
 

struct Node* constructBST(long long int postorder[], long long int start, long long int end)
{
    // base case
    if (start > end) {
        return NULL;
    }
    struct Node* node = newNode(postorder[end]);
 
    long long int i,j;
    long long int diff,number;
    diff=end-start;
    number=1;

    if(diff<50){
        for (i = end; i >=start; i--)
        {
        if (postorder[i] < node->key) {
            break;
        }
        }
    }
    else{
        diff=diff/10;
        while(diff>10)
        {
            diff=diff/10;
            number=number*10;
        }
        for(j=end;j>=start;j=j-number)
        {
            if (postorder[j] < node->key) {
                break;
            }
        }
        for(i=j+number;i>=j;i--)
        {
            if (postorder[i] < node->key) {
                break;
            }
        }

    }


 
    node->right = constructBST(postorder, i + 1, end - 1);
    node->left = constructBST(postorder, start, i);
    return node;
}