uva 536 - Tree Recovery

点击打开链接uva 536

思路: 二叉树
分析:
1 题目给定前序序列和中序序列，要求二叉树的后序序列
2 建好二叉树之和直接遍历输出即可，裸题

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 30;

char preOrder[MAXN];
char midOrder[MAXN];

struct Node{
    char c;
    Node *left;
    Node *right;
    Node(char c){
        this->c = c;
        this->left = left;
        this->right = right;
    }
};
Node *root;

Node* createTree(char *pre , char *mid , int len){
     if(len == 0) 
         return NULL;
     int k = 0;
     while(mid[k] != pre[0])
         k++;
     Node *root = new Node(pre[0]);
     root->left = createTree(pre+1 , mid , k);
     root->right = createTree(pre+k+1 , mid+k+1 , len-k-1);
     return root;
}

void output(Node *u){
    if(u != NULL){
        output(u->left); 
        output(u->right); 
        printf("%c" , u->c);
    }
}

void solve(){
    int len = strlen(preOrder); 
    root = createTree(preOrder , midOrder , len);
    output(root);
    puts("");
}

int main(){
   while(scanf("%s" , preOrder) != EOF){
        scanf("%s" , midOrder);   
        solve();
   }
   return 0;
}