fork download
copy 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. typedef struct _node{
  4.     int value;
  5.     struct _node *left;
  6.     struct _node *right;
  7. }Node;
  8. int *pre, *in, n;
  9. void buildTree(Node* root, int ins, int pres, int num){
  10.     if(num == 1)return;
  11.     int p = 0;
  12.     for(int i=ins; i<ins+num; i++){
  13.         if(in[i] == root->value) p = i;
  14.     }
  15.     if(p>ins){
  16.         pres += 1; num += (1-p);
  17.         Node* leftchild = (Node*)malloc(sizeof(Node));
  18.         leftchild->value = pre[pres];
  19.         root->left = leftchild;
  20.         leftchild->left = NULL; leftchild->right = NULL;
  21.         buildTree(leftchild,ins,pres,num);
  22.     }
  23.     if(p<ins+num-1){
  24.         num += (ins-p); pres += (p+1-ins); ins = (p-ins+1); 
  25.         Node* rightchild = (Node*)malloc(sizeof(Node));
  26.         rightchild->value = pre[pres];
  27.         root->right = rightchild;
  28.         rightchild->left = NULL; rightchild->right = NULL;
  29.         buildTree(rightchild,ins,pres,num);
  30.     }
  31. }
  32. void print_in_post_order(Node* root){
  33.     if(root != NULL){
  34.         print_in_post_order(root->left);
  35.         print_in_post_order(root->right);
  36.         printf("%d ",root->value);
  37.         free(root);
  38.     }
  39. }
  40. int main(){
  41.     scanf("%d",&n);
  42.     pre = (int*)malloc(sizeof(int)*n);
  43.     in = (int*)malloc(sizeof(int)*n);
  44.     for(int i=0; i<n; i++)scanf("%d",&in[i]);
  45.     for(int i=0; i<n; i++)scanf("%d",&pre[i]);
  46.     Node* root = (Node*)malloc(sizeof(Node));
  47.     root->value = pre[0]; root->left = NULL; root->right = NULL;
  48.     buildTree(root,0,0,n);
  49.     print_in_post_order(root);
  50.     printf("\n");
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0s 4360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/qrerI8
language:
C (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!