洛谷-UVA536 二叉树重建 Tree Recovery

女爷i 2023-06-18 14:55 5阅读 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;
    }

[PDF]: https://uva.onlinejudge.org/external/5/p536.pdf
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubHVvZ3UuY29tLmNuL3VwbG9hZC92anVkZ2VfcGljL1VWQTUzNi8zMTg4MGQ4MzI4NGY4ODE1MmJjM2NlZDEzMmU0NGEwNTkyODc4NDFkLnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubHVvZ3UuY29tLmNuL3VwbG9hZC92anVkZ2VfcGljL1VWQTUzNi82Y2Y5NjQxYmViYTE4ZGFjYjkxYTU0MjI5MTg4ZmI0NzZhYTgxNDIyLnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubHVvZ3UuY29tLmNuL3VwbG9hZC92anVkZ2VfcGljL1VWQTUzNi81ODllMTU3NDFhZmMzMmNiZDc3ZGEyNzhlOGU3MmNlM2Q1ZGJkNjcwLnBuZw?x-oss-process=image/format,png