题目
见官网
思路
这道题建树，遍历平平无奇。只是有两点需要注意：
- 根节点的位置需要自己寻找：未出现在别人孩子位置的节点即为根节点
- 在输出时，括号需要稍作处理。通过观察可以发现，中序遍历输出时，非根非叶节点需要输出括号。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 23;
struct node {
string data;
int lchild, rchild;
}Node[maxn];
int n;
int flag[maxn];
void inorder(int root) {
if (root == -1) return;
if (flag[root] == 1 && ( Node[root].lchild != -1 || Node[root].rchild != -1)) cout<<"(";
inorder(Node[root].lchild);
cout<<Node[root].data;
inorder(Node[root].rchild);
if (flag[root] == 1 && (Node[root].lchild != -1 || Node[root].rchild != -1)) cout<<")";
}
int main() {
cin>>n;
for (int i = 1; i <= n; i++) {
cin>>Node[i].data>>Node[i].lchild>>Node[i].rchild;
if (Node[i].lchild != -1) flag[Node[i].lchild] = 1;
if (Node[i].rchild != -1) flag[Node[i].rchild] = 1;
}
int root = 0;
for (int i = 1; i <= n; i++) {
if (flag[i] != 1) {
root = i;
break;
}
}
inorder(root);
}
