思路与算法

扩展前序串中每个非点字符是实节点，点表示空子树。用显式栈存尚未完成的节点及阶段：0表示尚未完成左子树，1表示左子树已完成而等待右子树。读到实节点就入栈；读到空子树后向上汇报完成：阶段0节点此时输出到中序并改为阶段1，阶段1节点此时输出到后序并弹栈，再继续向其父节点汇报。

正确性说明

前序编码先给根，再给完整左子树和右子树。栈始终表示当前未完成节点链。完成左子树时根字符恰好处于左、右子树之间，所以写入中序正确；完成右子树时两个孩子均已结束，此时写根到后序正确。空子树不产生字符，只触发完成事件。每个实节点恰好经历一次阶段转换和一次弹栈，因此两种序列都无遗漏重复。

复杂度

设扩展串长度L、实节点数N。每个字符读取一次、每节点入出栈各一次，时间O(L+N)=O(L)。栈最大深度O(N)，两份输出与输入总空间O(L)。动态容器初始O(1)，字符追加的摊还时间包含在总界内，使用显式栈避免深链耗尽递归调用栈。

易错点

空节点在样例中用半角.编码，不是字母；中序与后序分别一行，不输出空节点标记。输入根为空时输出两个空行。不能仅凭不含空标记的一个前序串恢复任意二叉树。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Frame {
    char c;
    int stage;
};
int main() {
    string s;
    cin >> s;
    vector<Frame> st;
    string in, post;
    for (char c : s) {
        if (c != '.') {
            st.push_back({c, 0});
            continue;
        }
        while (!st.empty()) {
            if (st.back().stage == 0) {
                in += st.back().c;
                st.back().stage = 1;
                break;
            }
            post += st.back().c;
            st.pop_back();
        }
    }
    cout << in << '\n' << post << '\n';
}