c101 - 00122 - Trees on the level
題目描述
題目要求讀取二元樹的節點資訊，並按照階層順序輸出樹的節點值。輸入以節點的 (值, 路徑) 形式表示，路徑由 'L' (左) 和 'R' (右) 組成。輸入結束時以 "()" 表示。如果輸入的節點無法構成完整的二元樹（例如，缺少節點或路徑重複），則輸出 "not complete"。
解題思路
程式使用深度優先搜尋 (DFS) 建立二元樹，並使用 map 儲存節點的路徑和值。DFS 遍歷輸入的節點，並檢查路徑是否重複。在讀取 "()" 時，程式會檢查是否所有節點都已包含在樹中。如果樹是完整的，則程式會執行階層順序遍歷，並輸出節點值。
複雜度分析
- 時間複雜度: O(N)，其中 N 是節點的數量。這是因為程式需要遍歷所有節點來建立樹和執行階層順序遍歷。
- 空間複雜度: O(N)，其中 N 是節點的數量。這是因為 map 儲存所有節點的路徑和值，並且
e陣列在最壞情況下可能需要儲存所有節點。
程式碼
#include <bits/stdc++.h>
using namespace std;
int n,ct,ma;
map <string,int> mp;
string s;
bool rp;
vector <int> e[100005];
void dfs(string ns,int lv){
if(mp.find(ns)==mp.end())return;
ma=max(ma,lv);
ct++;
e[lv].push_back(mp[ns]);
dfs(ns+'L',lv+1);
dfs(ns+'R',lv+1);
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
while(cin >> s){
if(s=="()"){
if(rp){
cout << "not complete\n";
}
else{
dfs("",0);
if(ct!=mp.size()){
cout << "not complete\n";
}
else{
bool st=0;
for(int i=0;i<=ma;++i){
for(int j=0;j<e[i].size();++j){
if(st)cout << " ";
cout << e[i][j];
st=1;
}
}
cout << "\n";
}
memset(e,0,sizeof(e));
}
rp=0;
ct=0;
mp.clear();
continue;
}
int tmp=0,i;
string ts;
for(i=1;s[i]!=',';++i){
tmp*=10;
tmp+=s[i]-'0';
}
for(++i;s[i]!=')';++i){
ts+=s[i];
}
if(mp.find(ts)!=mp.end()){
rp=1;
}
mp[ts]=tmp;
}
}