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

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
int n;
int indg[N];
struct Node
{
    int l,r;
}e[N];

void dfs1(int u)
{
    if(u==0)return;
    cout<<u<<' ';
    dfs1(e[u].l);
    dfs1(e[u].r);
}


void dfs2(int u)
{
    if(u==0)return;
    dfs2(e[u].l);
    cout<<u<<' ';
    dfs2(e[u].r);
}


void dfs3(int u)
{
    if(u==0)return;
    dfs3(e[u].l);
    dfs3(e[u].r);
    cout<<u<<' ';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        if(e[u].l==0)e[u].l=v;
        else e[u].r = v;
        indg[v]++;
    }

    for(int i=1;i<=n;i++)
    {
        if(e[i].l==0&&e[i].r==0)continue;
        else if(e[i].l==0||e[i].r==0)
        {
            int mx = max(e[i].l,e[i].r);
            if(mx>i)
            {
                e[i].l = mx;
                e[i].r = 0;
            }
            else
            {
                e[i].r = mx;
                e[i].l = 0;
            }
        }
        else 
        {
            int mx = max(e[i].l,e[i].r);
            int mn = min(e[i].l,e[i].r);
            e[i].l = mn;
            e[i].r = mx;
        }
    }
    int root = 0;
    for(int i=1;i<=n;i++)
    {   
        if(indg[i]==0)
        {
            root = i;
            break;
        }

    }

    dfs1(root);
    cout<<'\n';
    dfs2(root);
    cout<<'\n';
    dfs3(root);
    return 0;
}

这道题目就是正常的进行先中后序遍历，问题在于正确建树，左孩子与右孩子按照题目要求进行构建，即可