DFS
$O(n)$
考点:二叉树的中序遍历,根节点的确定(根节点入度为0)
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
typedef struct{
char val[50];
int left;
int right;
} Node;
int n;
bool st[30];
Node nodes[30];
char res[1000];
int root;
void dfs(int r){
if(nodes[r].left == -1 && nodes[r].right == -1){
strcat(res, nodes[r].val);
return;
}
if(r != root) strcat(res, "(");
if(nodes[r].left != -1){
dfs(nodes[r].left);
}
strcat(res, nodes[r].val);
if(nodes[r].right != -1){
dfs(nodes[r].right);
}
if(r != root) strcat(res, ")");
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
int l, r;
scanf("%s %d %d", nodes[i].val, &l, &r);
nodes[i].left = l, nodes[i].right = r;
if(l != -1) st[l] = true;
if(r != -1) st[r] = true;
}
//找出根节点
for(int i = 1; i <= n; i++){
if(!st[i]){
root = i;
break;
}
}
dfs(root);
puts(res);
return 0;
}