hzCPPOJ

求二叉树的先序遍历

时间限制:  1 s      内存限制:   128 MB
提交:87     正确:73     分值:90

题目描述

出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度≤8)


输入

2行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序排列。

输出

1行,表示一棵二叉树的先序遍历

样例

样例输入:
BADC BDCA
样例输出:
ABCD
样例输入:
DBAECFG DBEGFCA
样例输出:
ABDCEFG

提示

先在后序中找到最后面的节点A,那我们知道这棵树的根目录是AA将中序的遍历分成两个部分前面部分"B"是左子树的中序遍历,后面部分"DC"是右子树的中序遍列

在后序遍历中找到这两个字符串中最后出现的字符,那就是左子树和右子树的根节点,再在中序遍历中划分…..

提交人

lixun2017

来源/分类