c126 - 00536 - Tree Recovery
題目描述
題目給定一個二元樹的前序遍歷和中序遍歷的字串，要求重建這棵二元樹，並輸出其後序遍歷的字串。
解題思路
本題的核心思想是利用前序和中序遍歷的特性來遞迴地重建二元樹。前序遍歷的第一个节点是樹根，在中序遍歷中找到樹根，則可以將中序遍歷分割成左子樹和右子樹。然後遞迴地重建左子樹和右子樹。
具體步驟如下：
- 從前序遍歷中取出第一個節點作為樹根。
- 在中序遍歷中找到樹根節點，根據樹根節點將中序遍歷分割成左子樹和右子樹。
- 根據左子樹的節點數，從前序遍歷中取出左子樹的節點，遞迴地重建左子樹。
- 根據右子樹的節點數，從前序遍歷中取出右子樹的節點，遞迴地重建右子樹。
- 最後，以左子樹、右子樹、樹根的順序輸出後序遍歷。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是樹的節點數。這是因為在每次遞迴調用中，我們都需要在長度為 n 的中序遍歷字串中查找樹根節點，這需要 O(n) 的時間。
- 空間複雜度: O(n)，其中 n 是樹的節點數。這是因為我們需要使用遞迴調用堆疊來存儲中間結果，最壞情況下，遞迴深度為 n。
程式碼
#include <iostream>
using namespace std;
struct tree{
char v;
tree *r;
tree *l;
};
string a,b;
tree* bt(int pre,int mid,int l){
if(l<=0)return NULL;
tree *T=new tree;
T->v=a[pre];
int i=0;
while(a[pre]!=b[mid+i]){
++i;
}
T->l=bt(pre+1,mid,i);
T->r=bt(pre+i+1,mid+i+1,l-i-1);
return T;
}
void f(tree* t){
if(t==NULL)return;
if(t->l!=NULL)f(t->l);
if(t->r!=NULL)f(t->r);
cout << t->v ;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> a >> b){
tree *head=bt(0,0,a.length());
f(head);
cout << "\n";
}
}