考察:DFS进行中序遍历。
注意:给除了根节点以外的父节点加左右括号。
AC代码
#include<cstdio>
#include<iostream>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>using namespace std;const int maxn = 21;int n;struct Node{string str;int lchild,rchild;
}node[maxn];int vis[maxn] = {0};int R;int findRoot(){int root;for(int i=1;i<=n;i++){if(vis[i]==0){root = i;break;}}return root;
}void DFS(int root){if(root==NULL)return;if(root!=R&&(node[root].lchild!=-1||node[root].rchild!=-1))printf("(");if(node[root].lchild!=-1)DFS(node[root].lchild);printf("%s",node[root].str.c_str());if(node[root].rchild!=-1)DFS(node[root].rchild);if(root!=R&&(node[root].lchild!=-1||node[root].rchild!=-1))printf(")");return;
}int main(){cin>>n;for(int i=1;i<=n;i++){string str;int l,r;cin>>str>>l>>r;node[i].str = str;node[i].lchild = l;vis[l] = 1;node[i].rchild = r;vis[r] = 1;}R = findRoot();DFS(R);return 0;
}