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

存储结构

可以采用数组存储法。

• 使用 vector<int> v(2 * n + 2, -1) 来存储每个节点的左右子节点。

• 对于节点 u：

• v[2 * u] 存储其左子节点。

• v[2 * u + 1] 存储其右子节点。

• 这种方式比传统的结构体指针更节省内存分配时间。

根节点识别

在一棵树中，根节点是唯一一个没有父节点的节点。

• 使用 vis 数组记录所有在输入中作为“子节点”出现过的编号。
• 最后遍历 1 到 n，未被标记的节点即为 root。

自动排序逻辑

在 pushEdge 函数中，可加入一个简单的判断：

• 如果一个父节点已经有一个子节点，新加入的子节点会与原有的进行大小比较，确保较小的数值放在左侧，较大的放在右侧。

遍历顺序

理解三种遍历方式的关键在于根节点相对于左右子树的访问顺序：

• 先序遍历：根 左 右
• 中序遍历：左 根 右
• 后序遍历：左 右 根

代码实现

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

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

    int n;
    cin >> n;
    vector<int> v(2 * n + 2, -1);
    vector<bool> vis(n + 1, false);

    auto pushEdge = [&](int a, int b) {
        if (v[2 * a] != -1) {
            if (v[2 * a] < b) {
                v[2 * a + 1] = b;
            } else {
                v[2 * a + 1] = v[2 * a];
                v[2 * a] = b;
            }
        } else {
            v[2 * a] = b;
        }
        vis[b] = true;
    };

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        pushEdge(a, b);
    }

    int root = -1;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            root = i;
            break;
        }
    }

    auto preOrder = [&](auto&& self, int u) {
        if (u == -1) return;

        cout << u << " ";

        if (v[2 * u] != -1) {
            self(self, v[2 * u]);
        }
        if (v[2 * u + 1] != -1) {
            self(self, v[2 * u + 1]);
        }
    };

    auto inOrder = [&](auto&& self, int u) {
        if (u == -1) return;

        if (v[2 * u] != -1) {
            self(self, v[2 * u]);
        }

        cout << u << " ";

        if (v[2 * u + 1] != -1) {
            self(self, v[2 * u + 1]);
        }
    };


    auto postOrder = [&](auto&& self, int u) {
        if (u == -1) return;

        if (v[2 * u] != -1) {
            self(self, v[2 * u]);
        }
        if (v[2 * u + 1] != -1) {
            self(self, v[2 * u + 1]);
        }

        cout << u << " ";
    };

    preOrder(preOrder, root);
    cout << "\n";
    inOrder(inOrder, root);
    cout << "\n";
    postOrder(postOrder, root);
    cout << "\n";
}

复杂度分析

• 时间复杂度：。构建树需要 ，每种遍历访问每个节点恰好一次，总时间为线性。
• 空间复杂度：。主要开销为存储子节点的 v 数组以及递归时的系统栈。