题解 | 先序遍历、中序遍历和后序遍历

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

const int N=1e5+10;
int n,root;
vector<int> child[N];
vector<int> l(N+1,0),r(N+1,0);
vector<bool> hashfa(N+1,false);

void dfs_xian(int x){
	cout<<x<<" ";
	if(l[x]!=0) dfs_xian(l[x]);
	if(r[x]!=0) dfs_xian(r[x]);
	return;
}

void dfs_zhong(int x){
	if(l[x]!=0) dfs_zhong(l[x]);
	cout<<x<<" ";
	if(r[x]!=0) dfs_zhong(r[x]);
	return;
}

void dfs_hou(int x){
	if(l[x]!=0) dfs_hou(l[x]);
	if(r[x]!=0) dfs_hou(r[x]);
	cout<<x<<" ";
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n;
	int x,y;
	for(int i=1;i<=n-1;i++){
		cin>>x>>y;
		child[x].push_back(y);
		hashfa[y]=true;
	}
	
	for(int i=1;i<=n;i++){
		if(!hashfa[i]){
			root=i;
			break;
		}
	}
	for(int i=1;i<=n;i++){
		if(child[i].size()==2){
			l[i]=min(child[i][0],child[i][1]);
			r[i]=max(child[i][0],child[i][1]);
		}else if(child[i].size()==1){
			if(child[i][0]>i){
				l[i]=child[i][0];
			}else{
				r[i]=child[i][0];
			}
		}
	}
	dfs_xian(root);cout<<endl;
	dfs_zhong(root);cout<<endl;
	dfs_hou(root);cout<<endl;
    return 0;
}