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

#include <bits/stdc++.h>
#include<cmath>
using namespace std;
int n;
unordered_map<int, vector<int>>a;
vector<int>l(1010),r(1010);
vector<bool>hf(1010);

void PreOrder(int root) 
{
    cout<<root<<" ";
    if(l[root]!=0)PreOrder(l[root]);
    if(r[root]!=0)PreOrder(r[root]);
}
void InOrder(int root)
{
    if(l[root]!=0)InOrder(l[root]);
    cout<<root<<" ";
    if(r[root]!=0)InOrder(r[root]);
}
void ReOrder(int root)
{
    if(l[root]!=0)ReOrder(l[root]);
    if(r[root]!=0)ReOrder(r[root]);
    cout<<root<<" ";
}

int main() {
    cin>>n;
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x].push_back(y);
        hf[y]=true;
    }
    int root=-1;
    for(int i=1;i<=n;i++)
    {
        if(!hf[i])
        {
            root=i;
        }
        if(a[i].size()==1)
        {
            if(a[i][0]>i)
            {
                l[i]=a[i][0];
            }
            else{
                r[i]=a[i][0];
            }
        }
        else if(a[i].size()==2)
        {
            l[i]=min(a[i][0],a[i][1]);
            r[i]=max(a[i][0],a[i][1]);
        }
    }
    PreOrder(root);
    cout<<endl;
    InOrder(root);
    cout<<endl;
    ReOrder(root);
    return 0;
}