d432 - 第四題：通關密語 (pwd)

🔗 前往 ZeroJudge 原題

題目描述

題目給定一棵二元樹的中序遍歷和後序遍歷結果，要求重建這棵二元樹並輸出其前序遍歷結果，也就是通關密語。

解題思路

這題的核心是利用中序和後序遍歷重建二元樹。後序遍歷的最後一個元素一定是根節點。有了根節點，就可以在中序遍歷中找到根節點，並將中序遍歷分割成左子樹和右子樹。然後遞迴地對左子樹和右子樹進行相同的操作，直到重建出整棵樹。重建完成後，對重建的樹進行前序遍歷即可得到通關密語。

程式碼中，index 陣列用於儲存每個字元在中序遍歷中的位置，方便快速查找根節點。dfs 函數實現了遞迴重建二元樹和前序遍歷的功能。

複雜度分析

• 時間複雜度: O(n^2)，其中 n 是字串的長度。這是因為在 dfs 函數中，每次查找最大值需要遍歷字串的一部分，而 dfs 函數會被調用 n 次。
• 空間複雜度: O(n)，主要用於儲存 index 陣列和遞迴調用的堆疊空間。

程式碼

#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 ;
}