cpp每日一題（1）——求先序序列

原題目

題目描述

給出一棵二叉樹的中序與後序排列。求出它的先序排列。（約定樹結點用不同的大寫字母表示，長度\(\le 8\)）

輸入格式

2行，均為大寫字母組成的字元串，表示一棵二叉樹的中序與後序排列。

輸出格式

1行，表示一棵二叉樹的先序。

解題思路

初步思路

• 定義node結構體表示樹結點，定義node類型的tree[]數組來存儲樹；
• 通過遞歸的方式根據樹的中序和後序序列來确定通路這棵樹；
• 最後用再對存儲好的樹通路其先序序列。

進一步考慮

簡易版代碼

#include<bits/stdc++.h>
using namespace std; 
string mid,last;
int len;
void dfs(int ml,int mr,int ll,int lr)//ml,mr定位中序序列，ll,lr定位後序序列 
{
	cout<<last[lr];
	int i;
	for(i=0;i<=len;i++)if(mid[i]==last[lr])break;//從中序序列中找到根結點位置
	if(i>ml)dfs(ml,i-1,ll,lr-mr+i-1);//兩序列下标的範圍是重點
	if(i<mr)dfs(i+1,mr,ll+i-ml,lr-1);//要很仔細地去模拟
}
int main()
{
	cin>>mid;
	cin>>last;
	len=mid.length()-1;
	dfs(0,len,0,len);
	return 0;
}
           

總結與反思