专栏首页从流域到海域校招必考:根据二叉树遍历序列确定二叉树

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

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

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

理论基础:

由二叉树的先序遍历序列(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左边则为其左子树,右边推导完毕。二叉树已经能够确定。
  • 现在你能求出这棵二叉树的后序遍历吗?

作者注:

  • 推导过程中序遍历是依据,先找根,找到根以后,根左边都是其右左子树,右边都是其右子树。中序和前序遍历出现矛盾以中序为准,说明这个根下面可能只有右子树。
  • 每个结点都是一个根,所以推导任何一个结点的方法都相同(递归就是反复调用同一个方法)。
  • 二叉树遍历是递归进行的,所以我们才能通过递归的方法反向推导整棵树。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 深度学习中的范数

    我们知道距离的定义是一个宽泛的概念,只要满足非负、自反、三角不等式就可以称之为距离。

    Steve Wang
  • 《Java程序设计基础》 第4章手记

    《Java程序设计基础》 第4章手记 本章主要内容 - 语句和复合语句 - 分支结构 - 循环结构 - 跳转语句 这四部...

    Steve Wang
  • 《笨办法学Python》 第5课手记

    《笨办法学Python》 第5课手记 本节内容复习了前两节的内容,并且引入了格式化字符,这节课里的格式化字符与C语言格式化字符,规则没有什么区别。 我把原文代码...

    Steve Wang
  • Android SystemUI(一):图文并茂的介绍 :D

    菜天哥哥
  • .NET Core的日志[1]:采用统一的模式记录日志

    记录各种级别的日志是所有应用不可或缺的功能。关于日志记录的实现,我们有太多第三方框架可供选择,比如Log4Net、NLog、Loggr和Serilog 等,当然...

    蒋金楠
  • 用python做时间序列预测三:时间序列分解

    时间序列的各个观测值可以是以上成分相加或相乘得到: Value = Trend + Seasonality + Error Value = Trend * ...

    程序员一一涤生
  • iOS经典错误library not found for -lXXX

    VV木公子
  • 洛谷1638(尺取)

    可是,那里的博览馆有一个很奇怪的规定,就是在购买门票时必须说明两个数字,a和b,代表他要看展览中的第 a 幅至第 b 幅画(包含 a 和 b)之间的所有图画,而...

    ACM算法日常
  • 五,ESP8266 TCP服务器多连接(基于Lua脚本语言)

    一些时间去准备朋友的元器件了... 接着写,,争取今天写完所有的文章,,因为答应了朋友下周5之前要做好朋友的东西 对于TCP大家在玩AT指令的时候有没有发现客户...

    杨奉武
  • 每日一题:三次握手与四次挥手上篇

    今天来聊聊面试频率特别高的一个题目:TCP 协议中的三次握手与四次挥手。涉及到的知识点有:

    用户7685359

扫码关注云+社区

领取腾讯云代金券