专栏首页章鱼的慢慢技术路笔试常考题型之二叉树的遍历

笔试常考题型之二叉树的遍历

一、介绍

在互联网公司的笔试题中,经常会出现给出一个二叉树的前序和中序遍历,让你去求它的后序遍历问题,因此我将这类题型的解题步骤总结如下。

二、例题

题目解析:

注:此题中f节点的爸爸是d。

前序遍历顺序 根->左->右:abefd。

中序遍历顺序 左->根->右:ebadf。

后序遍历顺序 左->右->根:ebfda。

题目解析:

二叉搜索树有一个很重要的特性:树中任何结点的左子树中所有结点的值均比该结点小,右子树中所有结点的值均比该结点大。对二叉搜索树进行中序遍历即得到一个递增排序的序列。

因此,检查一个树是否是二叉搜索树可以使用中序遍历,根据递增排序的序列生成二权搜索树也可以使用中序遍历。

参考资料:二叉搜索树的简单介绍 二叉排序_搜索_查找树 C++

题目解析:

1,先序遍历的第一个节点肯定是根节点,所以A为该二叉树的根节点。

2,中序遍历中根节点左侧的节点全是根节点左子树的节点,根节点右侧的节点全是根节点的右子树。所以我们可以分成 DCB(左) | A(根) | EFG(右)。

3,递归使用上述两个步骤,可以画出整个二叉树。

(1)先得出A是根节点。

(2)DCB是A左子树中的点,EFG是A右子树中的点。

(1)B是A左子树的根节点,E是A右子树的根节点。

(2)CD是B左子树中的点,FG是E右子树中的点。

(1)C是B左子树的根节点,F是E右子树的根节点。

(2)D是C左子树中的点,G是F右子树中的点。

因此该二叉树的后序遍历为(左->右->根):DCBGFEA。

三、解题感受

遇到这种问题,记得先找出根节点,然后找出根节点左边的节点和根节点右边的节点,然后以此类推,找出根节点左子树的根节点和右子树的根节点...最后可以根据前序和中序遍历画出一个二叉树,再根据画出的二叉树(前提是要保证之前的步骤都正确)求出后序遍历。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 笔试常考题型之二叉树的遍历

    Zoctopus
  • 数据结构与算法笔试面试题整理

    b.对每一对相邻的元素做同样的工作,从开始的第一对一致到结尾的最后一对,经过这一步,最后的元素将是最大值;

    Zoctopus
  • Go指南练习_映射

    Zoctopus
  • 笔试常考题型之二叉树的遍历

    Zoctopus
  • 二叉树的四种遍历算法

    二叉树在作为一种重要的数据结构,它的很多算法的思想在很多地方都用到了,比如说大名鼎鼎的 STL 算法模板,里面的优先队列(priority_queue)、集合(...

    指点
  • 深度优先和广度优先的Python实现

    py3study
  • 【学术】当你开始深度学习时,请注意这些事情

    深度学习为数据科学提供了非常有效的工具,几乎可以解决任何领域的问题,并使用任何类型的数据。然而,深度学习算法的非直观性推导和使用需要非常仔细的实验设计,如果不能...

    AiTechYun
  • Co-LncRNA:lncRNA与蛋白编码基因的共表达网络数据库

    有多项研究表明lncRNA与众多生物学过程,复杂疾病相关,为了进一步探究lncRNA在这些生命活动中的具体作用,我们需要对lncRNA的功能进行分析。

    生信修炼手册
  • 布尔值数组的状态压缩

    二维矩阵可以不产生一个图结构,直接在二维矩阵上计算。相应地,会设定一个布尔值数组visited[ i ] [ j ],表示某一个位置是否被遍历,true表示被遍...

    我脱下短袖
  • 打卡群2刷题总结1010——二叉树的层序遍历

    https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

    木又AI帮

扫码关注云+社区

领取腾讯云代金券