d861 - NOIP2001 3.求先序排列

🔗 前往 ZeroJudge 原題

題目描述

題目給定一棵二叉樹的中序排列和後序排列，要求輸出該二叉樹的先序排列。樹的節點使用不同的大寫字母表示，樹的長度不超過 8。

解題思路

這題的核心思想是利用二叉樹的三種遍歷方式（先序、中序、後序）之間的關係。後序遍歷的最後一個節點是二叉樹的根節點。在中序遍歷中找到根節點，就可以將二叉樹分割成左子樹和右子樹。然後遞歸地對左子樹和右子樹進行相同的操作，直到所有節點都被遍歷。

具體步驟如下：

1. 建立一個 index 陣列，用於儲存後序遍歷中每個節點在中序遍歷中的位置。
2. 定義一個遞迴函數 dfs，接受左邊界 it 和右邊界 it2 作為參數。
3. 在 dfs 函數中，找到 in[it] 到 in[it2] 範圍內在中序遍歷中值最大的節點，這個節點就是根節點。
4. 將根節點添加到先序排列 pre 中。
5. 遞迴地對左子樹進行 dfs 遍歷，左子樹的範圍是 [it, mit-1]。
6. 遞迴地對右子樹進行 dfs 遍歷，右子樹的範圍是 [mit+1, it2]。

複雜度分析

• 時間複雜度: O(n^2)
• 空間複雜度: O(n)

程式碼

#include <iostream>
using namespace std;
string in,po,pre;
int l,index[301];
void dfs(int it,int it2){
	if(it2<0||it>it2)return;
	int ma=-1,mit=-1;
	for(int i=it;i<=it2;++i){
		if(index[in[i]]>ma){
			ma=index[in[i]];
			mit=i;
		}
	}
	pre+=in[mit];
	dfs(it,mit-1);
	dfs(mit+1,it2);
}
int main(){
	cin >> in >> po;
	l=in.length();
	for(int i=0;i<l;++i)
		index[po[i]]=i;
	dfs(0,l-1);
	cout << pre ;
}