代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5 + 10; 
struct Node{
	int ls,rs;
}a[maxn];

void dfs(int u){
	if(u=='*') 
		return;
	cout << u;
	dfs(a[u].ls);
	dfs(a[u].rs);
}

int main(){   
	int n,r;
	cin >> n;
	for(int i=1;i<=n;i++){
		int x,y,z;
		cin >> x >> y >> z;
		if(i==1) {
			r=x;
		}
		a[x].ls = y;
		a[x].rs = z;
	}
	dfs(r);
}

题目：

二叉树的中序遍历

题目描述

给你一个大小为$n$的树，输出此树的中序遍历

输入格式

第一行一个整数$n$表示大小为$n$的树

接下来一共$n$行每行有两个整数$a,b$ 第 $i$行表示 点$i$的左子节点是$a$，右子节点是$b$，倘若$a或b$为 $-1$则说明没有此左儿子或者右儿子

输出格式

输出一行

样例 #1

样例输入 #1

4
2 3
4 -1
-1 -1
-1 -1

样例输出 #1

4213

提示

$n <= 10^5$