PP4865 根据扩展后序序列求先序（基础）

解题思路

第一步，理解"扩展后序序列"。 普通后序遍历的顺序是"左、右、根"。扩展后序把每个空结点也写成一个点 '.'，这样任意一棵二叉树都能用唯一一串字符表示。比如样例 "..a..bc.d" 就是一棵二叉树的扩展后序序列，要我们输出它的先序遍历结果 dcab。

第二步，从右往左看。 后序序列的最后一个字符一定是整棵树的根。读掉根之后，紧挨在它前面的，先是右子树的扩展后序，再是左子树的扩展后序。所以可以这样递归：每次从字符串末尾取一个字符，如果是 '.' 就返回空结点，否则建一个新结点，先递归建右子树，再递归建左子树。

第三步，注意递归顺序。 因为在字符串里右子树排在左子树前面，所以必须先 build 右子树再 build 左子树，顺序反了整棵树就建错了。建完整棵树后，用先序（根、左、右）输出。

第四步，例子验证。 对 "..a..bc.d"：最后一个字符 d 是根；它前面是 '.'，说明右子树为空；再往前递归建出左子树 c，c 的左孩子是 a、右孩子是 b。先序遍历：d、c、a、b，输出 dcab，与样例一致。

第五步，边界情况。 字符串长度最多 255，递归深度不会超过 255，不会爆栈。注意 '.' 代表空结点，只有字母才是真正的结点。

参考代码

// 根据扩展后序序列求先序：从右往左建树，再输出先序遍历
#include <iostream>
using namespace std;

struct Node {
    char ch;  // 结点字母
    Node* l;  // 左孩子
    Node* r;  // 右孩子
};

char s[300];
int idx;  // 当前读到的位置

// 建树：从 s 里取字符，返回建好的根节点
Node* build() {
    char c = s[idx--];
    if (c == '.') return NULL;  // '.' 表示空结点
    Node* nd = new Node;
    nd->ch = c;
    nd->r = build();  // 后序序列里右子树在左子树前面
    nd->l = build();
    return nd;
}

// 先序遍历：根、左、右
void pre(Node* nd) {
    if (nd == NULL) return;
    cout << nd->ch;
    pre(nd->l);
    pre(nd->r);
}

int main() {
    cin >> s;
    int len = 0;
    while (s[len]) ++len;  // 求字符串长度
    idx = len - 1;
    Node* root = build();
    pre(root);
    cout << endl;
    return 0;
}

复杂度分析

每个字符在递归中只被处理一次，所以时间复杂度是 O(L)，L 是序列长度；递归调用和 new 结点要占用 O(L) 空间。L 最大只有 255，运行非常快。