链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度 ≤ 8)。
输入描述:
2行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序排列。
输出描述:
1行,表示一棵二叉树的先序。
示例1
输入
复制BADC BDCA
BADC BDCA
输出
复制ABCD
ABCD
思路和题解
二叉树的定义是递归定义,很多二叉树题目的解决方法也可以是递归。二叉树的中序遍历是左->根->右,后序遍历是左->右->根,先序遍历是根->左->右。我们可以按照下面的步骤来解决问题。
1、如果一个树是空树,则退出。
2、输出二叉树的根,在中序排列中找到二叉树根的位置pos,即后序排列的最后一个字符在中序排列里的位置。在中序排列中pos的左边(假设字符个数为x)为左子树的中序排列,pos右边(假设字符个数为y)为右子树的中序排列。在后续排列中前x个字符组成的子串为左子树的后序排列,紧接着后面的y个字符组成的子串为右子树的后序排列。
3、对左子树的中序排列后续排列做步骤2文章来源:https://www.toymoban.com/news/detail-743146.html
4、对右子树的中序排列和后续排列做步骤2文章来源地址https://www.toymoban.com/news/detail-743146.html
代码:
#include<iostream>
#include<cstring>
using namespace std;
string zhong,hou;
void f(int l1,int r1,int l2,int r2)
{
int pos=-1;
if(l1>r1) return ;
//找根节点在中序序列中的位置
for(int i=l1;i<=r1;i++)
if(zhong[i]==hou[r2])
{pos=i;break;}
cout<<hou[r2];
f(l1,pos-1,l2,l2+(pos-1-l1));
f(pos+1,r1,l2+(pos-1-l1)+1,r2-1);
}
int main()
{
cin>>zhong>>hou;
int len=zhong.length();
f(0,len-1,0,len-1);
}
到了这里,关于求先序排列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!