根据前序和中序推出后序

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

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

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

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

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

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

递归下去就可以了

后序为bdcafge

扩展:

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

下面关于二叉搜索树的是否正确? 给定一棵二叉搜索树的前序和后序遍历结果,无法确定这棵二叉搜索树。

这个说法是错误的。

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏熊二哥

深入入门系列--Data Structure--04树

终于有机会重新回头学习一下一直困扰自身多年的数据结构了,赶脚棒棒哒。一直以来,对数据结构的掌握基本局限于线性表,稍微对树有一丢丢了解,而对于图那基本上就是不懂(...

1889
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题19二叉树的镜像

   分析:所谓“镜像”就是从镜子里看到的样子。我们可以画一棵二叉树,然后画出该二叉树的镜像。画完图之后我们会发现,所谓“二叉树的镜像”就是把二叉树中所有子树...

2835
来自专栏java学习

面试题65(树,图)

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

3054
来自专栏算法channel

基本算法|图解各种树(一)

01 — 二叉树 节点的度数不超过2的树,称为二叉树,如下图所示: ? ? 02 — 单链和满二叉树 含n个节点,高度为h的二叉树中,满足如下关系: h <...

3907
来自专栏Hongten

日历(Calendar)_java版(某年的日历,某月的日历)_用户完全自定义

========================================================

2452
来自专栏Python专栏

【数据结构与算法】一起搞定面试中的二叉树题目(二)

2073
来自专栏青玉伏案

算法与数据结构(十一) 平衡二叉树(AVL树)(Swift版)

今天的博客是在上一篇博客的基础上进行的延伸。上一篇博客我们主要聊了二叉排序树,详情请戳《二叉排序树的查找、插入与删除》。本篇博客我们就在二叉排序树的基础上来聊聊...

2447
来自专栏xingoo, 一个梦想做发明家的程序员

AVL树

平衡二叉树,是一个方便查找的树,树的左子树深度与右子树的深度的差总(BF)是在+1,0,-1之中。 随着树的建立,插入,树都会自动的进行调整,使得其满足上面的条...

2085
来自专栏苦逼的码农

【漫画】以后在有面试官问你AVL树,你就把这篇文章扔给他。

例如,我现在想要查找数值为14的节点。由于二叉查找树的特性,我们可以很快着找到它,其过程如下:

1485
来自专栏Micro_awake web

python二叉树递归算法之后序遍历,前序遍历,中序遍历

1 #!/usr/bin/env python 2 # -*- coding: utf-8 -*- 3 # @Date : 2016-11-18 0...

2545

扫码关注云+社区

领取腾讯云代金券