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

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

int fa[Maxn]={0};
int L[Maxn]={0},R[Maxn]={0};
bool vis[Maxn]={false};
void pre(int root)
{
     if(root == 0)
        return;
    int l = min(L[root],R[root]),r=max(L[root],R[root]);
    if(R[root] == 0)
    {
        if(r<root)
        {
            L[root] = 0;
            R[root] = r;
        }
    }
    else {
        L[root] = l;
        R[root] = r;
    }
    cout<<root<<' ';
    pre(L[root]);
    pre(R[root]);
    return;
}

void mid(int root)
{
    if(root == 0)
        return;
    mid(L[root]);
    cout<<root<<' ';
    mid(R[root]);
    return;
}

void last(int root)
{
    if(!root)
        return;
    last(L[root]);
    last(R[root]);
    cout<<root<<' ';
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    int n,root;
    cin>>n;
    int u,v;
    for(int i=1;i<n;++i)
    {
        cin>>u>>v;
        vis[v] = true;
        if(L[u] == 0)
            L[u] = v;
        else
         R[u] = v;

    }
    for(int i=1;i<=n;++i)
    {
        if(!vis[i])
            {
                root = i;
                break;
            }
    }
    pre(root);
    cout<<'\n';
    mid(root);
    cout<<'\n';
    last(root);
}