校招必考:根据二叉树遍历序列确定二叉树

2024-01-19 18:58

本文主要是介绍校招必考:根据二叉树遍历序列确定二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

根据二叉树的前序遍历和中序遍历求其后序遍历或者根据二叉树的后序遍历和中序遍历求其前序遍历是腾讯等校招的必考题,下面我们就来分析一下解题思路。


这道题本质上是要我们根据二叉树遍历序列确定二叉树,只要二叉树确定了,求它的任何遍历序列都是易如反掌的。

理论基础:

由二叉树的先序遍历序列(PreorderTraverse)和中序遍历序列(InorderTraverse)或由其后序遍历序列(PostorderTraverse)和中序遍历序列均能唯一地确定一棵二叉树。

求解过程:
1. 先序序列第一个结点一定是二叉树的根节点
2. 根节点在中序序列中必然将中序序列分割为两个子序列,前一个序列为根节点的左子树的中序序列,后一个序列为根节点的右子树的中序序列。
3. 递归使用以上两条法则,直到序列只剩下一个结点。

如果是后序序列和中序序列,那么步骤1改为后序序列的最后一个结点一定是二叉树的根结点。

例:已知结点的先序序列和中序序列分别为:
先序序列:18 14 7 3 11 22 35 27
中序序列:3 7 11 14 18 22 27 35
则可按上述分解求得整棵二叉树。

  • 18为根结点 中序序列分割为 3 7 11 14 18 22 27 35 左右两部分 18的左子树是14 右子树是22。
    这里写图片描述
  • 左边3 7 11 14中,14是根,3 7 11都在其左边,因此都是14的左子树,14没有右子树。
  • 再由先序序列18 14 7 3 11得, 7是14的左子树。
  • 左边3 7 11, 7 是根,3在7左边即为其左子树,11在7右边即为其右子树,左边推导完毕。
  • 这里写图片描述
  • 右边22 24 35,则24、35都是22的右子树。
  • 再看前序序列22 35 27, 35是22的左子树与上面矛盾,则22没有左子树,35是22的右子树
  • 右边 24 35,24在35左边则为其左子树,右边推导完毕。二叉树已经能够确定。
    这里写图片描述

    • 现在你能求出这棵二叉树的后序遍历吗?

作者注:

  • 推导过程中序遍历是依据,先找根,找到根以后,根左边都是其右左子树,右边都是其右子树。中序和前序遍历出现矛盾以中序为准,说明这个根下面可能只有右子树。

  • 每个结点都是一个根,所以推导任何一个结点的方法都相同(递归就是反复调用同一个方法)。

  • 二叉树遍历是递归进行的,所以我们才能通过递归的方法反向推导整棵树。

这篇关于校招必考:根据二叉树遍历序列确定二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/623366

相关文章

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现

如何确定哪些软件是Mac系统自带的? Mac系统内置应用查看技巧

《如何确定哪些软件是Mac系统自带的?Mac系统内置应用查看技巧》如何确定哪些软件是Mac系统自带的?mac系统中有很多自带的应用,想要看看哪些是系统自带,该怎么查看呢?下面我们就来看看Mac系统内... 在MAC电脑上,可以使用以下方法来确定哪些软件是系统自带的:1.应用程序文件夹打开应用程序文件夹

利用Python实现时间序列动量策略

《利用Python实现时间序列动量策略》时间序列动量策略作为量化交易领域中最为持久且被深入研究的策略类型之一,其核心理念相对简明:对于显示上升趋势的资产建立多头头寸,对于呈现下降趋势的资产建立空头头寸... 目录引言传统策略面临的风险管理挑战波动率调整机制:实现风险标准化策略实施的技术细节波动率调整的战略价

python进行while遍历的常见错误解析

《python进行while遍历的常见错误解析》在Python中选择合适的遍历方式需要综合考虑可读性、性能和具体需求,本文就来和大家讲解一下python中while遍历常见错误以及所有遍历方法的优缺点... 目录一、超出数组范围问题分析错误复现解决方法关键区别二、continue使用问题分析正确写法关键点三

PostgreSQL 序列(Sequence) 与 Oracle 序列对比差异分析

《PostgreSQL序列(Sequence)与Oracle序列对比差异分析》PostgreSQL和Oracle都提供了序列(Sequence)功能,但在实现细节和使用方式上存在一些重要差异,... 目录PostgreSQL 序列(Sequence) 与 oracle 序列对比一 基本语法对比1.1 创建序

Java遍历HashMap的6种常见方式

《Java遍历HashMap的6种常见方式》这篇文章主要给大家介绍了关于Java遍历HashMap的6种常见方式,方法包括使用keySet()、entrySet()、forEach()、迭代器以及分别... 目录1,使用 keySet() 遍历键,再通过键获取值2,使用 entrySet() 遍历键值对3,

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库(STL)提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,:本文主要介绍C... 目录(1)容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌(基于哈希表):‌容器适配器‌:(