P4871 二叉树的遍历（入门）

解题思路

第一步，读入并保存树的结构。 题目给出一棵二叉树，第 i 行的结点编号就是 i，每行有结点的字母和它的左右孩子编号，编号 0 表示没有孩子。用数组 lef[i]、rig[i] 记录左右孩子，用 val[i] 记录字母。编号 1 的结点是根，所以从 1 号开始遍历。

第二步，写先序遍历。 先序的顺序是"根、左子树、右子树"。函数 pre(u) 先输出 val[u]，再递归访问 lef[u]，最后递归访问 rig[u]。遇到编号 0 说明没有孩子，直接返回。

第三步，写中序遍历。 中序的顺序是"左子树、根、右子树"。函数 ino(u) 先递归左孩子，再输出自己，最后递归右孩子。

第四步，写后序遍历。 后序的顺序是"左子树、右子树、根"。函数 post(u) 先递归左孩子，再递归右孩子，最后输出自己。

类比一下。 三种遍历就像整理一摞文件：先序是"先拿封面，再看左边抽屉、再看右边抽屉"；中序是"先看左边抽屉，再看封面，再看右边抽屉"；后序是"看完两个抽屉，最后才拿封面"。顺序不同，结果就不同。

边界情况。 如果某结点没有左或右孩子（编号 0），递归到它时函数第一行就返回，不会越界，也不会输出多余字符。

参考代码

// 二叉树三种遍历：数组存左右孩子，递归输出先序/中序/后序
#include <iostream>
using namespace std;

int lef[30], rig[30];   // 左右孩子编号，0表示没有
char val[30];           // 结点值

// 先序：根左右
void pre(int u) {
    if (u == 0) return;
    cout << val[u];
    pre(lef[u]);
    pre(rig[u]);
}

// 中序：左根右
void ino(int u) {
    if (u == 0) return;
    ino(lef[u]);
    cout << val[u];
    ino(rig[u]);
}

// 后序：左右根
void post(int u) {
    if (u == 0) return;
    post(lef[u]);
    post(rig[u]);
    cout << val[u];
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> val[i] >> lef[i] >> rig[i];
    pre(1);
    cout << endl;
    ino(1);
    cout << endl;
    post(1);
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度。 三种遍历每个结点都恰好访问一次，每次操作是常数时间，所以总时间复杂度是 O(n)。n 最大只有 26，非常快。

空间复杂度。 除了存树结构的大小为 n 的数组，递归深度等于树的高度，最坏是 O(n)，所以空间复杂度是 O(n)。