解题思路
这题如果非叶子节点无左孩子,要先输出根节点,在遍历右儿子
cpp代码
#include<iostream>
#include<unordered_map>
using namespace std;
const int N=10000;
string w[N];
int l[N],r[N];
int n;
string ch[N];
int cnt;
unordered_map<int,int> Hash;
void dfs(int u){
if(!~u)return ;
ch[cnt++]='(';
if(l[u]==-1){
ch[cnt++]=w[u];
dfs(r[u]);
}
else{
dfs(l[u]);
dfs(r[u]);
ch[cnt++]=w[u];
}
ch[cnt++]=')';
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
string a;int b,c;
cin>>a>>b>>c;
w[i]=a;
l[i]=b;
r[i]=c;
Hash[b]=i;
Hash[c]=i;
}
if(n==1){
cout<<"(";
cout<<w[1];
cout<<")";
return 0;
}
int root=1;
while(Hash.count(root))root=Hash[root];
dfs(root);
for(int i=0;i<cnt;i++)cout<<ch[i];
}