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

#include<bits/stdc++.h>
#define endl "\n"
#define int long long
using namespace std;
void slove() {
    int n;
    std::cin >> n;
    std::vector<std::vector<int>> edge(n + 1);
    std::vector<std::pair<int, int>> a(n + 1);
    std::vector<int> vis(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        edge[u].push_back(v);
        vis[v] = 1;
    }
    int root = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            root = i;
            break;
        }
    }
    auto build = [&](auto&& build, int x)->void{
        if (edge[x].size() == 2) {
            int l = std::min(edge[x][0], edge[x][1]);
            int r = std::max(edge[x][0], edge[x][1]);
            a[x].first = l;
            a[x].second = r;
            build(build, l);
            build(build, r);
        } else if (edge[x].size() == 1) {
            if (edge[x][0] > x) {
                a[x].first = edge[x][0];
            } else {
                a[x].second = edge[x][0];
            }
            build(build, edge[x][0]);
        }
    };
    build(build, root);
    // for(int i=1;i<=n;i++) std::cout<<i<<" "<<a[i].first<<" "<<a[i].second<<endl;
    auto pre = [&](auto&& pre, int x)->void{
        std::cout << x << " ";
        if (a[x].first != 0) pre(pre, a[x].first);
        if (a[x].second != 0) pre(pre, a[x].second);
    };
    pre(pre, root);
    std::cout << endl;
    auto mid = [&](auto&& mid, int x)->void{
        if (a[x].first != 0) mid(mid, a[x].first);
        std::cout << x << " ";
        if (a[x].second != 0) mid(mid, a[x].second);
    };
    mid(mid, root);
    std::cout << endl;
    auto suf = [&](auto&& suf, int x)->void{
        if (a[x].first != 0) suf(suf, a[x].first);
        if (a[x].second != 0) suf(suf, a[x].second);
        std::cout << x << " ";
    };
    suf(suf, root);
}
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T = 1;
    //std::cin>>T;
    while (T--)    {
        slove();
    }
    return 0;
}

用stl里面的pair根据规则建立一颗二叉树。然后就是最基础的递归思路。注意根的查找即可，水一篇题解（）