求先序排列

这篇具有很好参考价值的文章主要介绍了求先序排列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

链接:登录—专业IT笔试面试备考平台_牛客网

来源:牛客网  

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

复制BADC BDCA

BADC
BDCA

输出

复制ABCD

ABCD

思路和题解

二叉树的定义是递归定义,很多二叉树题目的解决方法也可以是递归。二叉树的中序遍历是左->根->右,后序遍历是左->右->根,先序遍历是根->左->右。我们可以按照下面的步骤来解决问题。

1、如果一个树是空树,则退出。

2、输出二叉树的根,在中序排列中找到二叉树根的位置pos,即后序排列的最后一个字符在中序排列里的位置。在中序排列中pos的左边(假设字符个数为x)为左子树的中序排列,pos右边(假设字符个数为y)为右子树的中序排列。在后续排列中前x个字符组成的子串为左子树的后序排列,紧接着后面的y个字符组成的子串为右子树的后序排列。

3、对左子树的中序排列后续排列做步骤2

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数学建模比赛题型划分、常用算法及其适用场景

    题型划分、常用算法及其适用场景 常见赛题类型 优化类 机理分析类 评价类 预测类 算法体系分类 数据处理模型 优化模型 预测模型 评价模型 聚类分析模型 常用算法分类 数据预处理模型及应用场景 1.插值拟合 主要用于对数据的补全处理; 其中 样本点较少时 (泛指样本点小

    2024年02月10日
    浏览(46)
  • 【算法】——全排列算法讲解

    前言: 今天,我给大家讲解的是关于全排列算。我会从三个方面去进行展开: 首先,我会给大家分析关于全排列算法的思想和定义; 紧接着通过手动实现出一个全排列代码来带大家见见是怎么实现的; 最后我会给出两道题帮助大家去进行理解记忆。 目录 前情摘要 (一)定

    2024年02月09日
    浏览(37)
  • 算法刷题Day 29 递增子序列+全排列+全排列II

    如果直接像下面这样写的话,会出错,出错的案例类似: [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9nrEEc2S-1688623883770)(LC491-递增子序列+LC.assets/image-20230703201315163.png)] 本题求自增子序列,是不能对原数组进行排序的,排完序的数组都是自增子

    2024年02月15日
    浏览(43)
  • 力扣--深度优先算法/回溯算法47.全排列 Ⅱ

    思路分析: 使用DFS算法进行全排列,递归地尝试每个可能的排列方式。 使用 path 向量保存当前正在生成的排列,当其大小达到输入数组的大小时,将其加入结果集。 使用 numvisited 向量标记每个数字是否已经被访问过,以确保每个数字在一个排列中只使用一次。 在递归过程中

    2024年03月13日
    浏览(51)
  • 算法--排列组合

    2024年02月16日
    浏览(38)
  • 贪心算法:排列算式

    给出n数字,对于这些数字是否存在一种计算顺序,使得计算过程中数字不会超过3也不会小于0?

    2024年04月12日
    浏览(33)
  • 回溯算法篇-01:全排列

    这道题属于上一篇——“回溯算法解题框架与思路”中的 “元素不重复不可复用” 那一类中的 排列类问题。 我们来回顾一下当时是怎么说的: 排列和组合的区别在于,排列对“顺序”有要求。比如 [1,2] 和 [2,1] 是两个不同的结果。 这就导致了同一个元素 在同一条路径中不

    2024年01月20日
    浏览(31)
  • java实现排列组合算法

    我这里只写了组合的算法。         假设现有 M=4 个数据 a,b,c,d。从中随机抽取n个数,n为1—4个数据进行组合。那么数学中的计算组合方式为C(4,1) + C(4,2) + C(4,3) + C(4,4)  = 4 + 6 + 4 + 1 = 15。那么共有15种组合方式。 方案一:此方法容易理解但是效率慢         我的做

    2024年02月13日
    浏览(48)
  • 递归算法学习——全排列

    目录 ​编辑 一,问题描述 1.例子: 题目接口:  二,问题分析和解决 1.问题分析 2.解题代码 首先我们得来先看看全排列的问题描述。全排列问题的问题描述如下: 给定一个不含重复数字的数组  nums  ,返回其  所有可能的全排列  。你可以  按任意顺序  返回答案。 1.例

    2024年02月11日
    浏览(40)
  • 【算法题】47. 全排列 II

    给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。 示例 1: 输入:nums = [1,1,2] 输出: [[1,1,2],  [1,2,1],  [2,1,1]] 示例 2: 输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]   提示: 1 = nums.length = 8 -10 = nums[i] = 10 来自力扣官方题解

    2024年02月01日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包