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

一、介绍

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

二、例题

题目解析:

注:此题中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 条评论
登录 后参与评论

相关文章

来自专栏10km的专栏

java nio: walkFileTree实现文件夹复制移动删除

从java 1.7开始,java提供了java.noi.file.Files类用于更方便的实现文件/文件夹操作。 在Files中提供了丰富的静态方法用于文件...

2868
来自专栏Golang语言社区

golang把文件复制到另一个目录

//本程序 主要功能是把A文件夹下的文件与B目录下文件对比,如果找到就覆盖到B相应的目录下。 // 用法: merge A目录 B目录 // merge....

35112
来自专栏技术之路

visual studio 2012 的制作ActiveX、打包和发布

开发环境是Vs 2012  Framework 4.0 源码和制作工具在文章最下边 一. ActiveX控件Demo 新建一个Window窗体控件库项目 ? 在...

1809
来自专栏晓晨的专栏

Entity Framework Core 2.0 使用入门

1493
来自专栏Hadoop实操

如何使用java代码通过JDBC连接Hive(附github源码)

前面我们讲过《如何使用java代码通过JDBC连接Impala(附Github源码)》,本篇文章主要讲述如何使用Java代码通过JDBC的方式连接Hive。

5605
来自专栏木宛城主

SharePoint 2013 Backup Farm Automatically With a Powershell and Windows Task Schedule

In this post,I will show you SharePoint 2013 How to Backup Farm Automatically w...

1847
来自专栏SpringBoot 核心技术

第三十一章:SpringBoot配置文件application.properties参数详解

1524
来自专栏游戏杂谈

XCode打包脚本

配置之后,执行上面的脚本就会在.xcodeproject目录下生成debug、release的ipa

1013
来自专栏依乐祝

[译]ASP.NET Core Web API 中使用Oracle数据库和Dapper看这篇就够了

文章地址: https://www.cnblogs.com/yilezhu/p/9276565.html

881
来自专栏张高兴的博客

张高兴的 Windows 10 IoT 开发笔记:无线收发芯片 nRF24L01

1022

扫码关注云+社区