根据扩展后序序列求先序

题目描述

给定一棵二叉树的扩展后序序列，试构造这个二叉树，并输出这个二叉树的先序遍历结果。

输入格式

一行字符，即扩展后序序列，字符只包含小写字母和"."，长度不超过255。

输出格式

输出对应的先序遍历结果。

样例输入 #1

..a..bc.d

样例输出 #1

dcab

数据范围

扩展后序序列长度不超过255，字符只包含小写字母和"."。"."表示空节点。

知识点与难度

本题涉及的知识点从属于 GESP六级（二叉树、遍历、递归构造），难度等级：Mid。

测试点分布