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

一、介绍

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

二、例题

题目解析:

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

相关文章

来自专栏武培轩的专栏

剑指Offer-重建二叉树

题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,...

3508
来自专栏从流域到海域

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

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

1875
来自专栏从流域到海域

二叉排序树(BSTree)关于查找算法结合

/*基于树的顺序查找法*/ /*二叉排序树的存储结构*/ typedef struct node { KeyType key; ...

1667
来自专栏恰同学骚年

剑指Offer面试题:5.重建二叉树

  在二叉树的前序遍历序列中,第一个数字总是树的根结点的值。但在中序遍历序列中,根结点的值在序列的中间,左子树的结点的值位于根结点的值的左边,而右子树的结点的值...

834
来自专栏日常分享

Java 通过先序中序序列生成二叉树

  二叉树的前序以及后续序列,以空格间隔每个元素,重构二叉树,最后输出二叉树的三种遍历方式的序列以验证。

791
来自专栏开发与安全

数据结构:二叉树的定义和性质以及特殊二叉树

一、二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树...

1747
来自专栏尾尾部落

[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal [LeetCode] Construct Bina

链接:https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder...

604
来自专栏猿人谷

根据前序和中序推出后序

最近面试总遇到这种根据给出的两类序遍历,然后求按另一种形式序的遍历。看来有必要好好总结下这个知识点,省的每次笔试时都得花不少时间推导。 首先,我们看看前序、中序...

1726
来自专栏Petrichor的专栏

leetcode: 96. Unique Binary Search Trees

634
来自专栏java学习

面试题65(树,图)

面试例题1:前序遍历二叉树值为abcdefg,下面哪个不可能是中序遍历?A.abcdefg B.gfedcba C.bcdefga D.bceadfg 正确解析...

2714

扫码关注云+社区