题目描述

求一棵二叉树的前序遍历，中序遍历和后序遍历

输入格式

第一行一个整数 $n$，表示这棵树的节点个数。接下来 $n$ 行每行 $2$ 个整数 $L$ 和 $R$。
第 $i$行的两个整数 $L_i$和 $R_i$ 代表编号为 $i$ 的节点的左儿子编号和右儿子编号。

输出格式

输出一共三行，分别为前序遍历，中序遍历和后序遍历。编号之间用空格隔开。

样例

输入 #1

5
2 3
4 5
0 0
0 0
0 0

输出 #1

1 2 4 5 3
4 2 5 1 3
4 5 2 3 1

数据范围与提示

$n \le 100$，默认结点 $1$ 为树根。

#include<bits/stdc++.h>
using namespace std;

int n, d[100005], ans;
vector<int> v[100005];  //开了100005行

void dfs(int x, int xu){
	if(xu == 1) cout << x << ' ';
	if(v[x][0]) dfs(v[x][0], xu);
	if(xu == 2) cout << x << ' ';
	if(v[x][1]) dfs(v[x][1], xu);
	if(xu == 3) cout << x << ' ';
}
int main(){
	cin >> n;
	for(int i=1; i<=n; i++){
		int x, y;
		cin >> x >> y;
		v[i].push_back(x);  //把x加到i后面
		v[i].push_back(y);  //把y加到i后面
	}
	
	dfs(1, 1);
	cout << endl;
	dfs(1, 2);
	cout << endl;
	dfs(1, 3);
	return 0;
}