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

按先中后的顺序遍历就行了，因为是有向边，所以入度为0的为树的根

vector<vector<int>>e(N);
int d[N];
void dfs1(int x){//root left right
    cout<<x<<" ";
    if(e[x].empty())return ;
    sort(e[x].begin(),e[x].end());
    if(e[x].size()==1){
        dfs1(e[x][0]);
    }else{
        dfs1(e[x][0]);
        dfs1(e[x][1]);
    }
}
void dfs2(int x){//left root right
    if(e[x].empty()){
        cout<<x<<" ";
        return ;
    }
    if(e[x].size()==1){
        if(e[x][0]>x){
            dfs2(e[x][0]);
            cout<<x<<" ";
        }else{
            cout<<x<<" ";
            dfs2(e[x][0]);
        }
    }else{
        dfs2(e[x][0]);
        cout<<x<<" ";
        dfs2(e[x][1]);
    }
}
void dfs3(int x){//left root right
    if(e[x].empty()){
        cout<<x<<" ";
        return ;
    }
    if(e[x].size()==1){
        dfs3(e[x][0]);
        cout<<x<<" ";
    }else{
        dfs3(e[x][0]);
        dfs3(e[x][1]);
        cout<<x<<" ";
    }
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        d[v]++;
    }
    int root;
    for(int i=1;i<=n;i++){
        if(d[i]==0)root=i;
    }
    dfs1(root);cout<<'\n';
    dfs2(root);cout<<'\n';
    dfs3(root);
}