题目描述

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

输入格式

扩展二叉树的先序序列。

输出格式

输出其中序和后序序列。

数据范围

原二叉树的结点数不超过26，且均由大写字母表示。

输入样例：

ABD..EF..G..C..

输出样例：

DBFEGAC
DFGEBCA

#include<iostream>

using namespace std;

int k;
string str,in,post,pre;
//现给出扩展二叉树的先序序列，要求输出原二叉树中序和后序序列。
void dfs()
{
    if(str[k] == '.')//过滤掉
    {
        k++;
        return;
    }
    char r = str[k++];//根节点
    pre+=r;//前序
    dfs();//左子树
    in+=r;//中序
    dfs();//右子树
    post+=r;//后序
}

int main()
{
    cin>>str;
    dfs();
    cout<<in<<endl<<post<<endl;
    return 0;
}