P4873 根据扩展先序序列求中序和后序（基础）

解题思路

第一步，看懂"扩展先序序列"。 普通二叉树只存有值的结点，扩展二叉树把空子树也补一个"."。先序遍历遇到空子树就输出一个"."。比如 ABD..EF..G..C..，两个点连在一起表示某个结点没有孩子。

第二步，递归建树。 用一个全局下标 idx 从左往右读字符。函数 build() 先读一个字符 c：如果是 .，说明是空子树，返回 0；如果是大写字母，就新建一个结点，然后递归建左子树、再递归建右子树，最后返回这个结点编号。

第三步，想想为什么能建出来。 扩展先序里每个字母后面一定跟着它的左子树和右子树（可能是空"."）。按顺序读，读到字母就建结点，读到"."表示这里没有孩子，往回退。整个过程像照着说明书拼积木。

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

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

举个例子。 序列 ABD..EF..G..C..：A 是根，B 是 A 的左孩子，D 是 B 的左孩子，D 的两个"."表示 D 没有孩子。按这个规律能拼出整棵树，跑一遍中序得到 DBFEGAC，跑一遍后序得到 DFGEBCA，与样例一致。

边界情况。 序列长度不超过 53，数组开到 60 足够。遇到"."返回 0 是关键，保证不会越界或无限递归。

参考代码

// 扩展先序建树：'.'为空结点，递归建树后输出中序和后序
#include <iostream>
using namespace std;

char s[60];
int idx;          // 当前读到的下标

struct Node {
    char v;
    int lef, rig;  // 左右孩子在数组中的下标
} t[60];
int tot;          // 已建结点个数

// 递归建树，返回结点下标，空结点返回0
int build() {
    char c = s[idx++];
    if (c == '.') return 0;
    int u = ++tot;
    t[u].v = c;
    t[u].lef = build();   // 建左子树
    t[u].rig = build();   // 建右子树
    return u;
}

// 中序输出
void ino(int u) {
    if (u == 0) return;
    ino(t[u].lef);
    cout << t[u].v;
    ino(t[u].rig);
}

// 后序输出
void post(int u) {
    if (u == 0) return;
    post(t[u].lef);
    post(t[u].rig);
    cout << t[u].v;
}

int main() {
    cin >> s;
    int root = build();
    ino(root);
    cout << endl;
    post(root);
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度。 建树时每个字符恰好读一次，中序、后序遍历每个结点访问一次，总时间复杂度 O(n)，n 是序列长度。n 最大 53，非常快。

空间复杂度。 字符数组和结点数组都是 O(n)，递归深度最坏是树的高度 O(n)，总空间复杂度 O(n)。