PP4868 新二叉树（入门）

解题思路

第一步，理解题意。 输入 n 行，每行三个字母：第一个是当前结点，后两个分别是它的左儿子和右儿子，用 * 表示没有这个儿子。题目保证第一行的结点是整棵树的根。要求输出这棵树的前序遍历。

第二步，想怎么存树。 结点都是字母，我们可以直接用字母本身当数组下标，开两个数组 lc 和 rc：lc[a] 记 a 的左儿子，rc[a] 记右儿子，0 表示空。这样查任何一个结点的儿子都非常方便。

第三步，记住根。 第一行读到的结点一定是根，把它记到 root 变量里。之后每行读三个字母 a、b、c，把 lc[a]、rc[a] 填好，遇到 * 就填 0，遇到字母就填字母本身。

第四步，前序遍历。 前序顺序是"根、左、右"：先输出当前结点，再递归左子树，再递归右子树。遇到空结点（值是 0）直接返回。

第五步，例子验证。 样例中 a 是根，左儿子 b、右儿子 c；b 的左儿子 d、右儿子 i；c 的左儿子 j、右儿子空。前序遍历：a、b、d、i、c、j，输出 abdicj，与样例一致。

参考代码

// 新二叉树：读入左右儿子，输出前序遍历，* 表示空结点
#include <iostream>
using namespace std;

int lc[128], rc[128];  // 用字母本身做下标，0 表示空结点
int root;

// 前序遍历：根、左、右
void pre(int x) {
    if (x == 0) return;
    cout << (char)x;
    pre(lc[x]);
    pre(rc[x]);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        char a, b, c;
        cin >> a >> b >> c;
        if (i == 0) root = a;  // 第一行的结点一定是根
        lc[(int)a] = (b == '*' ? 0 : (int)b);
        rc[(int)a] = (c == '*' ? 0 : (int)c);
    }
    pre(root);
    cout << endl;
    return 0;
}

复杂度分析

每个结点在前序遍历中只被访问一次，所以时间复杂度是 O(n)；数组大小固定，空间是 O(1)。n 最大 26，瞬间完成。