Skip to content

1109: 扩展二叉树

题目

题目描述

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

输入格式

一行,代表了扩展二叉树的前序遍历。有若干个整数或者 ‘.’,其中整数代表了一个节点及其编号,‘.’ 的含义如题中所述,是一个空节点。

输出格式

两行,你需要输出这棵树的中序遍历和后序遍历。不需要输出 ‘.

样例输入

1 2 4 . . 5 6 . . 7 . . 3 . .

样例输出

4 2 6 5 7 1 3 4 6 7 5 2 3 1

数据范围

对于 20% 的数据,整棵树最多有 10 个节点。

对于 60% 的数据,整棵树最多有 1000 个节点。

对于 100% 的数据,整棵树最多有 100000 个节点。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!