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

有向边（a, b）说明

刚开始没看清这个条件是 有向边，默认为无向的，还在想怎么这么难。 起初直接写了三个 DFS，试图在递归过程中处理父子左右关系（结果发现不会 -.-）， 后来发现这样思路不太行，不如把重点放在建图上。

此时再看题目，才发现：边是有向边！ 这样问题就简单多了： 只需要根据题目给定的规则，先建好二叉树结构，再做三种遍历即可。

下面是代码实现，部分位置做了简要注释。

C++ 实现代码

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    vector<int> l(n + 1), r(n + 1);          // 左右孩子
    vector<int> child[n + 1];                // 子节点列表
    vector<bool> hasFa(n + 1, false);        // 是否有父节点

    // 读入 n-1 条有向边
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        child[a].push_back(b);
        hasFa[b] = true;
    }

    // 寻找根节点（没有父节点的节点）
    int root = 1;
    for (int i = 1; i <= n; i++) {
        if (!hasFa[i]) {
            root = i;
            break;
        }
    }

    // 构建左右孩子关系
    for (int u = 1; u <= n; u++) {
        if (child[u].size() == 2) {
            // 有两个孩子：小的为左，大的为右
            int a = child[u][0];
            int b = child[u][1];
            l[u] = min(a, b);
            r[u] = max(a, b);
        } else if (child[u].size() == 1) {
            // 只有一个孩子
            int a = child[u][0];
            if (u > a) {
                // 子节点编号小于父节点 → 右孩子
                r[u] = a;
            } else {
                // 子节点编号大于父节点 → 左孩子
                l[u] = a;
            }
        }
    }

    // 先序遍历
    auto pre = [&](auto &&pre, int cur) -> void {
        cout << cur << " ";
        if (l[cur] != 0) pre(pre, l[cur]);
        if (r[cur] != 0) pre(pre, r[cur]);
    };

    // 中序遍历
    auto mid = [&](auto &&mid, int cur) -> void {
        if (l[cur] != 0) mid(mid, l[cur]);
        cout << cur << " ";
        if (r[cur] != 0) mid(mid, r[cur]);
    };

    // 后序遍历
    auto last = [&](auto &&last, int cur) -> void {
        if (l[cur] != 0) last(last, l[cur]);
        if (r[cur] != 0) last(last, r[cur]);
        cout << cur << " ";
    };

    pre(pre, root);
    cout << "\n";
    mid(mid, root);
    cout << "\n";
    last(last, root);

    return 0;
}

// 64 位输出请用 printf("%lld")