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

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

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

理论基础:

由二叉树的先序遍历序列(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 条评论
登录 后参与评论

相关文章

来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题39二叉树的深度

题目:输入一颗二叉树的根结点,求该树的深度。从根结点到叶结点一次经过的结点形成树的一条路径,最长路径的长度为树的深度。 分析:本题是一道典型的“分治法”。要...

32850
来自专栏软件开发 -- 分享 互助 成长

二叉排序树和平衡二叉树

二叉排序树又称二叉查找树或二叉搜索树。 它一棵空树或者是具有下列性质: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,...

219100
来自专栏C/C++基础

求二叉树的深度和宽度

题目: 输入一个二叉树的根节点,求该树的深度。从根节点到叶子节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度包含的节点数为为树的深度,即二...

24020
来自专栏赵俊的Java专栏

平衡二叉树

23550
来自专栏尾尾部落

[剑指offer] 二叉树的深度

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

9020
来自专栏编程理解

数据结构(一):二叉树

二叉树( binary tree )是有限节点集合构成的结构,其结构的递归定义为:

14520
来自专栏灯塔大数据

每周学点大数据 | No.24二叉搜索树回顾(一)

No.24期 二叉搜索树回顾(一) Mr. 王:接下来我们谈一谈外存查找结构。内存中的查找结构最典型的就是二查搜索树了。这里我们先来简单地认识一下关于二叉树...

36450
来自专栏xcywt

《大话数据结构》树以及赫夫曼编码的例子

第六章 树 6.2 树的定义 树(Tree)的n个结点的有限集。当n=0时,称为空树。 任意一个非空树中: 1)有且仅有一个特定的称为根(root)的结点 2)...

46060
来自专栏程序生活

二叉树的深度

题目描述 输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 代码实现 递归实现 # ...

27240
来自专栏desperate633

LintCode 平衡二叉树题目分析代码

给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是:一棵二叉树中每个节点的两个子树的深度相差不会超过1。

7720

扫码关注云+社区

领取腾讯云代金券