当前位置:首页 > 数据结构 > 二叉树 > 正文
SSOJ2466二叉树遍历
2337+

题目大意:给出一棵二叉树的中序遍历和层次遍历,输出该树的先序遍历。

题目描述

树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序,给定中序和其他一种遍历的序列就可以确定一棵二叉树的结构。

假设一棵二叉树一个结点用一个字符描述,现在给出中序和按层遍历的字符串,求该树的先序遍历字符串。

输入

输入共两行,每行是由字母组成的字符串(一行的每个字符都是唯一的),分别表示二叉树的中序遍历和按层遍历的序列。

输出

输出就一行,表示二叉树的先序序列。

样例输入

DBEAC
ABCDE

样例输出

ABDEC

解题思路

先序遍历,先输出根结点,再输出左子树,最后输出右子树。因此,需要先根据中序遍历找到根结点、左子树和右子树。找根结点,可以根据按层遍历解决,因为父亲结点肯定比儿子结点的层次遍历先输出,所有我们只需要在字符串中找层次遍历最先输出的那个字符,即是当前子树的根结点,左边的就是左子树,右边的就是右子树。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,

SSOJ2466二叉树遍历:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!