xzc最喜欢的二叉树 Apare_xzc

我出的第一道题

题目名称：XZC最喜欢的二叉树
题目时限：1000ms
最大内存：128M

题目描述：

        众所周知，树是XZC最喜欢的数据结构。 二叉树是树的一种，是每个节点的子节点个数都不超过2的树。经典的二叉树有：红黑树，替罪羊树，胜者树，败者树…二叉树的遍历方式也有很多种，如：层序遍历，先序遍历(有人也称作前序遍历)，中序遍历，后续遍历。
        今天，XZC给你出了一道题，题目如下：
给出二叉树的先序遍历和中序遍历，还原二叉树，得到后续遍历，并且求叶子节点的个数以及树的最大深度。

输入：

每个测试文件有多组数据。
输入文件的第一行是一个正整数T（T<=10）代表有T组数据
每组数据的输入有三行
第一行是一个数字n (n<=100)，代表二叉树节点的个数
第二行是二叉树的先序遍历，用一个字符串表示，每个字符代表一个节点的值
第三行是二叉树的中序遍历，用一个字符串表示，每个字符代表一个节点的值
（输入保证二叉树每个节点的值各不相同）

输出：

对于每组数据，
在一行输出”Case #x: “(不含引号)
在第二行输出二叉树的后序遍历(行末无空格)
在第二行输入该二叉树叶子节点的个数，具体格式见样例
在第三行输入该二叉树的层数，以及距离根节点最远的一层的叶子节点的值，若有多个符合条件的叶子节点，输入在先序遍历中序列最靠前的。
两组数据之间输出一个空行，最后一个样例后面不输入空行。

（样例解释可以参见下放的图片）

样例输入：

3
3
ABC
BAC
8
ABDFCEGH
BFDACGEH
21
ABDHIORSEJKCFLPQTUGMN
HDIROSBJEKAFPLTUQCMGN

样例输出：

Case #1:
该二叉树的后序遍历为：BCA
该二叉树的叶子节点个数为：2
该二叉树的层数为：2，最深的叶子节点的值为：B

Case #2:
该二叉树的后序遍历为：FDBGHECA
该二叉树的叶子节点个数为：3
该二叉树的层数为：4，最深的叶子节点的值为：F

Case #3:
该二叉树的后序遍历为：HRSOIDJKEBPUTQLFMNGCA
该二叉树的叶子节点个数为：9
该二叉树的层数为：7，最深的叶子节点的值为：U

case #1 和 case #2的图：

Case #3 的图：

AC愉快~