书接上级：

题目来源

B3642 二叉树的遍历 - 洛谷

题目描述

有一个 n(n≤106) 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 n），建立一棵二叉树（根节点的编号为 1），如果是叶子结点，则输入 0 0。

建好树这棵二叉树之后，依次求出它的前序、中序、后序列遍历。

输入格式

第一行一个整数 n，表示结点数。

之后 n 行，第 i 行两个整数 l、r，分别表示结点 i 的左右子结点编号。若 l=0 则表示无左子结点，r=0 同理。

输出格式

输出三行，每行 n 个数字，用空格隔开。

第一行是这个二叉树的前序遍历。

第二行是这个二叉树的中序遍历。

第三行是这个二叉树的后序遍历。

输入输出样例

输入 #1

7
2 7
4 0
0 0
0 3
0 0
0 5
6 0

输出 #1

1 2 4 3 7 6 5
4 3 2 1 6 5 7
3 4 2 5 6 7 1 

题目分析

这道题根据树的遍历可以分成三部分，为前序遍历，中序遍历，后序遍历。

遍历详情见：有关树的存储与二叉树的遍历-CSDN博客

前序遍历为根左右。

先输出自己，再输出左，然后返回到右

而中序遍历，则为判断自己的左节点是否遍历过了或是否为空，等自己左节点为空或被遍历后，输出自己，然后再看右节点。

最后后序遍历，用while循环，根节点的左与右节点都被遍历后或都为0时，则结束，否则执行while循环，如果自己的左与右节点都输出过或为空，则输出自己，标记自己。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
vector<int> t[maxn];
bool p[maxn];//中序遍历的标记数组 
bool st[maxn];//后序遍历的标记数组
int x1[maxn];
void dfs(int m) {
	if(m!=0) cout<<m<<" ";
	for(int i=0; i<t[m].size(); i++) {
		dfs(t[m][i]);
	}
}
void z(int m) {
	if(p[t[m][0]]==false) {
		cout<<m<<" ";
		p[m]=false;
		if(p[t[m][1]]!=false) {
			z(t[m][1]);
		}
		return;
	}
	for(int i=0; i<t[m].size(); i++) {
		if(i==0) {
			if(p[t[m][i]]!=false) {
				z(t[m][i]);
			}
		}
		if(p[m]!=false){
			cout<<m<<" ";
			p[m]=false;
		}
		if(i==1){
			if(p[t[m][i]]!=false) {
				z(t[m][i]);
			}
		}
	}
}
int main() {
	int n;
	cin>>n;
	for(int i=1; i<=n; i++) {
		st[i]=true;
		p[i]=true;
	}
	for(int i=1; i<=n; i++) {
		int l,r;
		cin>>l>>r;
		t[i].push_back(l);
		t[i].push_back(r);
	}
	dfs(1);//前序遍历 
	cout<<endl;
	z(1);//中序遍历 
	cout<<endl;
	int j=0;
	int x=1;
	x1[j]=x;
	while(st[t[1][0]]!=false||st[t[1][1]]!=false) {
		if(st[t[x][0]]==false&&st[t[x][1]]==false) {
			cout<<x<<" ";
			st[x]=false;
			while((st[t[x][0]]==false&&st[t[x][1]]==false)&&x!=1) {
				x=x1[--j];//返回 
			}
		} else {
			for(int i=0; i<t[x].size(); i++) {
				if(st[t[x][i]]!=false) {
					x=t[x][i];
					x1[++j]=x;
					break;
				}
			}
		}
	}//后序遍历 
	cout<<1;//输出根节点 
	return 0;
}