根据前序和中序推出后序

简介:

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

首先,我们看看前序、中序、后序遍历的特性: 
前序遍历:(根—>左—>右) 
    1.访问根节点 
    2.前序遍历左子树 
    3.前序遍历右子树 
中序遍历:(左—>根—> 
    1.中序遍历左子树 
    2.访问根节点 
    3.中序遍历右子树 
后序遍历:(左—>右—> 
    1.后序遍历左子树 
    2.后序遍历右子树 
    3.访问根节点

 

三序中知道其中两个就可以推出第三个,但前提是我们必须知道中序(这里是针对二叉树的,不包括二叉搜索树).因为:先序和后序给我们提供的信息是一样的--告诉我们谁是根节点,中序则告诉我们左右子树在哪儿。

例:已知先序为eacbdgf,中序为abcdefg,求后序。

由先序我们知道e为根节点,我们在中序中把左右子树括起来 --(abcd)e(fg)

同样对左子树abcd进行分析,先序为acbd,中序为abcd.--a(bcd)

递归下去就可以了

后序为bdcafge

 

扩展:

在2014年阿里实习生招聘试题中就有一个问题:

下面关于二叉搜索树的是否正确?

给定一棵二叉搜索树的前序和后序遍历结果,无法确定这棵二叉搜索树。

这个说法是错误的。

二叉树(不是搜索二叉树),必须是中根加上先根或者后根就能构造出树,但是,这里面说了是二叉搜索树,已经暗含中根了




本文转自夏雪冬日博客园博客,原文链接:http://www.cnblogs.com/heyonggang/p/3366417.html,如需转载请自行联系原作者

目录
相关文章
|
人工智能 Java 测试技术
二叉树通过前序中序来构建二叉树(炒鸡详细到每一步)
二叉树通过前序中序来构建二叉树(炒鸡详细到每一步)
|
2月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
31 0
|
6月前
|
存储 算法 编译器
技术经验解读:二叉树的遍历:先序中序后序遍历的递归与非递归实现及层序遍历
技术经验解读:二叉树的遍历:先序中序后序遍历的递归与非递归实现及层序遍历
45 0
|
7月前
二叉树刷题记(九-二叉搜索树中的中序后继-中序遍历)
二叉树刷题记(九-二叉搜索树中的中序后继-中序遍历)
|
存储 算法
二叉树的前序/中序/后序遍历—采用递归与迭代两种方法实现嗷
二叉树的前序/中序/后序遍历—采用递归与迭代两种方法实现嗷
|
前端开发
前端知识案例-二叉树的遍历(前序 中序 后序)
前端知识案例-二叉树的遍历(前序 中序 后序)
74 0
前端知识案例-二叉树的遍历(前序 中序 后序)
|
C++
【C++】二叉树的遍历:前序、中序、后序、层序
【C++】二叉树的遍历:前序、中序、后序、层序
219 0
【小白学算法】8.二叉树的遍历,前序、中序和后序
【小白学算法】8.二叉树的遍历,前序、中序和后序
【小白学算法】8.二叉树的遍历,前序、中序和后序
|
算法 Java BI
【算法】二叉树遍历算法总结:前序中序后序遍历
二叉树遍历是非常经典的算法题,也是二叉树的一道基础算法题。 但是在平常的笔试面试中,其出现的频率其实并不是特别的高,我推测是这种题目相对来说比较基础,算是一个基础知识点。 比如剑指offer中出现的后序遍历题目,是给出一个数字序列,让你判断是不是平衡二叉树后序遍历序列,这样出题的难度比直接让你写后序遍历难很多。 但是,二叉树遍历容易吗?在递归方法下,前中后序遍历都是一个思路,理解起来也比较容易。 但是只是用迭代的话,二叉树遍历其实是有难度的!,这也是为什么LeetCode会在这三题题目的下方写出进阶: 递归算法很简单,你可以通过迭代算法完成吗?这句话了。
386 0