#include<stdio.h>
#include<malloc.h>
#include<string.h>
void exit(int);
#define MAX 100
typedef struct node {
    char d;
    struct node *lchild, *rchild;
} Tnode;

void MK(char in[], char is, char ie, char pre[], char pres, char pree, Tnode **r) {
    int i;
    if(is > ie || pres > pree)
        *r = NULL;
    else {
        *r = malloc(sizeof(Tnode));
        (*r)->d = pre[pres];
        for(i = is; i <= ie; i++) {
            if(in[i] == pre[pres]) {
                MK(in, is, i - 1, pre, pres + 1, pres + i - is, &(*r)->lchild);
                MK(in, i + 1, ie, pre, pres + i - is + 1, pree, &(*r)->rchild);
                break;
            }
            if(i > ie) {
                printf("输入错误!\n");
                exit(1);
            }
        }
    }
}
void postorder(Tnode *r) {
    if(r) {
        postorder(r->lchild);
        postorder(r->rchild);
        printf("%c", r->d);
    }
}
int leaf(Tnode *r) {
    if(r == NULL)
        return 0;
    else if(r->lchild == NULL && r->rchild == NULL)
        return 1;
    else
        return leaf(r->lchild) + leaf(r->rchild);
}
int height(Tnode *r) {
    int h1, h2;
    if(r == NULL)
        return 0;
    else {
        h1 = height(r->lchild);
        h2 = height(r->rchild);
        return 1 + (h1 > h2 ? h1 : h2);
    }
}
void main() {
    Tnode *r = NULL;
    char in[MAX], pre[MAX];
    printf("请输入前序序列:\n");
    gets(pre);
    printf("请输入中序序列:\n");
    gets(in);
    MK(in, 0, strlen(in) - 1, pre, 0, strlen(pre) - 1, &r);
    printf("\n后序遍历序列为:\n");
    postorder(r);
    printf("\n叶结点的个数为:%d\n", leaf(r));
    printf("\n高度为:%d\n", height(r));
}