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

void mktx()
{
    int n;
    cin>>n;
    vector<int>l(n+1,0),r(n+1,0),d(n+1,0);
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        if(!l[a]) l[a]=b;
        else r[a]=b;
        d[b]++;
    }
    int root=0;
    for(int i=1;i<=n;i++)
    {
        if(l[i]&&r[i])
        {
            if(l[i]>r[i]) swap(l[i],r[i]);
        }
        else
        {
            if(l[i]&&l[i]<i) swap(l[i],r[i]);
        }
        if(!d[i]) root=i;
    }
    auto pre=[&](auto &&self,int x)->void
    {
        if(!x) return;
        cout<<x<<" ";
        self(self,l[x]);
        self(self,r[x]);
    };
    auto mid=[&](auto &&self,int x)->void
    {
        if(!x) return;
        self(self,l[x]);
        cout<<x<<" ";
        self(self,r[x]);
    };
    auto nxt=[&](auto &&self,int x)->void
    {
        if(!x) return;
        self(self,l[x]);
        self(self,r[x]);
        cout<<x<<" ";
    };
    pre(pre,root);
    cout<<'\n';
    mid(mid,root);
    cout<<'\n';
    nxt(nxt,root);
}