1340：【例3-5】扩展二叉树

【题目描述】
由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用·补齐，如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。

现给出扩展二叉树的先序序列，要求输出其中序和后序序列。

【输入】
扩展二叉树的先序序列。

【输出】
输出其中序和后序序列。

【输入样例】
ABD…EF…G…C…
【输出样例】
DBFEGAC
DFGEBCA

分析

1. 此题就是先建树，字符为 ‘.’ 时候，就是当前这个结点向下继续建树的终止条件，可以采用Node *left, *right，这种引用式的建树；也可以给结点进行编号，通过编号建树；参考上一题：1339：【例3-4】求后序遍历；

写法一

#include <bits/stdc++.h>

using namespace std;
struct Node {
    char val;
    Node *left, *right;
};
string pre;
int p = -1;

Node *createTree() {
    if (pre[++p] == '.')
        return nullptr;
    Node *node = new Node();
    node->val = pre[p];
    node->left = createTree();
    node->right = createTree();
    return node;
}

void inOrder(Node *t) {
    if (t == nullptr)
        return;
    inOrder(t->left);
    cout << t->val;
    inOrder(t->right);
}

void postOrder(Node *t) {
    if (t == nullptr)
        return;
    postOrder(t->left);
    postOrder(t->right);
    cout << t->val;
}

int main() {
    cin >> pre;
    Node *root = createTree();
    inOrder(root);
    puts("");
    postOrder(root);
    return 0;
}

写法二

思路同一，就是存储树的形式变了；
需注意，在建树的函数中用了一个局部变量res去取全局变量idx的值，供return使用（在递归向上回来的时候，return idx是错的，因为他是全局变量，在递归结束回去后，没有恢复到原来的时候（开始递归时候的idx值已经改变了），而函数的局部变量res，同递归同步，递归回来的时候，res还是原来开始向下的那个值，而idx已经变了）；如果直接return idx，就会造成构建树失败；

#include <bits/stdc++.h>

using namespace std;
struct Node {
    char val;
    int left, right;
};
Node node[10010];
string pre;
int p = -1, idx;//p指向字符串，idx为结点编号

int createTree() {
    int res;//很重要，下面的return用的，idx是全局变量，不能return使用
    if (pre[++p] == '.')
        return 0;
    res = ++idx;
    node[res].val = pre[p];
    node[res].left = createTree();
    node[res].right = createTree();
    return res;
}

void inOrder(int t) {
    if (t == 0)
        return;
    inOrder(node[t].left);
    cout << node[t].val;
    inOrder(node[t].right);
}

void postOrder(int t) {
    if (t == 0)
        return;
    postOrder(node[t].left);
    postOrder(node[t].right);
    cout << node[t].val;
}

int main() {
    cin >> pre;
    createTree();
    inOrder(1);
    puts("");
    postOrder(1);
    return 0;
}