洛谷-UVA536 二叉树重建 Tree Recovery-蒲公英云

洛谷-UVA536 二叉树重建 Tree Recovery

女爷i 2023-06-18 14:55 106阅读 0赞

题目描述

PDF

format_png

输入格式

format_png 1

输出格式

format_png 2

题意翻译

输入一棵二叉树的先序遍历和中序遍历序列，输出它的后序遍历序列。

输入输出样例

输入 #1复制

DBACEGF ABCDEFG
BCAD CBAD

输出 #1复制

ACBFGED
CDAB

方法一：超时了

#include<bits/stdc++.h>
using namespace std;
    string preorder;
    string     inorder;
void proorder(string pre,string in){
        //结束条件
    if(in.size()==0){//或者条件为pre.size()==0 
        return;
    }    
    int len=in.find(pre[0]);
    proorder(pre.substr(1,len),in.substr(0,len)); 
    proorder(pre.substr(len+1),in.substr(len+1));
    cout<<pre[0];//没有左子树、也没有右子树了 
}
int main(){
    while(true){
        cin>>preorder>>inorder;
        proorder(preorder,inorder);    
        cout<<endl;    
    } 
    return 0;
}

方法二：

#include<bits/stdc++.h>
using namespace std;
string preorder,inorder;
void postorder(int l1,int l2,int n){
    if(n<=0){
        return;
    }
    int len=inorder.find(preorder[l1])-l2;
    postorder(l1+1,l2,len);
    postorder(l1+len+1,l2+len+1,n-len-1);
    cout<<preorder[l1];    
}
int main(){
    while(cin>>preorder>>inorder){
        int len=preorder.size();
        //第一个参数为：先序开始下标
        //第二个参数为：后续开始下标
        //len为节点数 
        postorder(0,0,len);
        cout<<endl;
    }
    return 0;
}