hihocoder 1049 后续遍历

#include<iostream>  
#include<cstdio>  
#include<string>  
#include<cstdlib>  
#include<string.h>  
using namespace std;  
  
  
char preorder[30],midorder[30],endorder[30];  
typedef struct mynode Node;  
typedef Node* Tree;  
  
  
struct mynode  
{  
    char data;  
    struct mynode* left;  
    struct mynode* right;  
};  
  
  
  
  
int build(int left,int right,Tree &root)//更新了一下使用引用使结构更加清晰  
{  
    if(left>right)  
        return 0;  
    int i,j,flag = 1;  
    for(i=0; i<strlen(preorder); i++)  
    {  
        for(j=left; j<=right; j++)  
            if(preorder[i]==midorder[j])  
            {  
                flag = 0;  
                break;  
            }  
        if(!flag)  
            break;  
    }  
    root = (Node*)malloc(sizeof(Node));  
    if(root==NULL)  
    {  
        perror("malloc failed");  
        exit(1);  
    }  
    root->left = NULL;  
    root->right = NULL;  
  
  
    root->data = preorder[i];  
    build(left,j-1,root->left);  
    build(j+1,right,root->right);  
}  
  
  
void del(Tree root)  
{  
    if(root!=NULL)  
    {  
        del(root->left);  
        del(root->right);  
    }  
    if(root!=NULL)  
    {  
        free(root);  
        root = NULL;  
    }  
}  
int pos = 0;  
int endcal(Tree root)  
{  
    if(pos == strlen(preorder))  
        return 0;  
    if(root->left)  
    {  
        endcal(root->left);  
  
  
    }  
    if(root->right)  
    {  
        endcal(root->right);  
    }  
    endorder[pos++] = root->data;  
}  
  
  
int main()  
{  
  
  
    Tree root;  
    cin>>preorder>>midorder;  
    build(0,strlen(preorder)-1,root);  
    endcal(root);  
    cout<<endorder<<endl;  
    del(root);  
}  

代码可以AC不知道有没有内存泄漏 有错误请指出

下面是别人写的

#include<iostream>  
#include<cstdio>  
#include<cstdlib>  
#include<string.h>  
using namespace std;  
  
char preorder[30],inorder[30],endorder[30];  
  
void endcal(const char *pre,const char *in,int len)  
{  
    if(len<1)  
        return ;  
    int i=0;  
    while(in[i]!=pre[0])i++;  
    endcal(pre+1,in,i);  
    endcal(pre+i+1,in+i+1,len-i-1);  
    cout<<pre[0];  
}  
  
int main()  
{  
    cin>>preorder>>inorder;  
    endcal(preorder,inorder,strlen(preorder));  
}  

顺便给出前序遍历

#include<iostream>  
#include<cstdio>  
#include<cstdlib>  
#include<string.h>  
using namespace std;  
  
char pre[30],in[30],last[30];  
  
void precal(char *last,char *in,int lastend,int inend)  
{  
    if(lastend<0||inend<1)  
        return ;  
    int i=0;  
    while(in[i]!=last[lastend-1])i++;  
    cout<<last[lastend-1];  
    precal(last,in,lastend-inend+i,i);  
    precal(last,in+i+1,lastend-1,inend-i-1);  
}  
  
int main()  
{  
    while(cin>>last>>in)  
        precal(last,in,strlen(last),strlen(in)),putchar('\n');  
}