首页 > 试题广场 >

已知一个二叉树的后序遍历的结果为 AEFDHZMG, 那么它

[不定项选择题]
已知一个二叉树的后序遍历的结果为AEFDHZMG，那么它的中序遍历可能为（），前序遍历可能为（） 
  • ADEFHMGZ
  • ADEFGHMZ
  • GDAEFMHZ
  • GDAFEMHZ
查看正确选项
添加回答
hexiaosa头像 hexiaosa
选B,D；
G为根节点，M为右子树根节点，根据c,d选项可知D为左子树根节点，右子树中序应为HMZ（M根节点在中间），所以中序选b；
根据后序和中序遍历可知前序选d。

发表于 2017-03-08 21:33:24 回复(0)
沉浮一香蕉头像 沉浮一香蕉
根据题目得出G是根节点，所以B选项就是中序遍历，根据中序和后序结果构建出树，得到前序遍历结果。
发表于 2022-04-29 15:25:51 回复(0)
灬Prettysunshine头像 灬Prettysunshine
已知后序遍历是这么多，如果仅仅利用后序遍历推二叉树，则这棵树不只一种，所以还要结合ABCD选项来推出二叉树的形状，再完成最后结果。
发表于 2019-03-15 16:48:52 回复(0)
josan头像 josan
这题直接空着过来的  哈哈
发表于 2017-07-10 12:56:55 回复(0)
迎风~起头像 迎风~起
树结构如图，思路为：
寻找共同项，分别对比AB和CD
得到大致结构——
前序遍历：GDA _ _ MHZ
中序遍历：ADEF _ _ _ Z
后序遍历：AEFDHZMG
然后画个图往里填空就行
发表于 2017-08-11 19:30:52 回复(1)
雾z~霭头像 雾z~霭
由后序遍历知M一定是G的右孩子；故中序遍历一定是B。
由后续遍历知E一定是F 的孩子，故前序遍历中F一定在E前，选D
发表于 2018-03-08 22:36:19 回复(3)
InGodWeTrust头像 InGodWeTrust
答案为：BD
先假定一个中序遍历，如A
由于根节点是G，若为A则右子树为Z，则找不到前序遍历。
因此中序遍历为B，推得前序遍历为D
发表于 2017-04-06 16:08:17 回复(2)
救赎i_头像 救赎i_
由选项序列组成，可大致将AB、CD归为一组，根据题干给出的后序遍历序列可知树的根为G，可得CD中的某一个为前序遍历序列，而AB中的某一个就是中序遍历序列了。又因为G是根，在中序序列找到G，将它的左右序列就是它的左右子树，可知A的右子树是Z，根据后序遍历的规则：“左 右 根”，Z一定在G的前面，而题干给出的后序遍历序列Z不在G的前面，所以A错误，所以只有B可能为中序遍历序列。中序和后序可以唯一确定一颗二叉树，确定这棵二叉树后先序自然也就得到了。
发表于 2022-07-18 22:01:57 回复(0)
JCMaxwell头像 JCMaxwell
两个空是分别问的，所以第一个空填B、第二个空填CD才是正确答案，原题表述有误。
发表于 2019-05-12 10:00:13 回复(0)
牛客403090902号头像 牛客403090902号
这题不严谨啊，你们有没有考虑两个空是独立的情况？
发表于 2020-10-03 22:56:46 回复(0)
kitlen头像 kitlen
这种类型的题目一定要知道后序和中序  或  前序和中序 才能确定具体树。
所以根据题目中给出的后序，先要推出中序，然后结合推导出来的中序和已知的后序去推导前序。
发表于 2019-08-18 15:19:13 回复(0)
小目标头像 小目标
bd
发表于 2016-12-12 16:29:20 回复(0)
绝有丶白莲头像 绝有丶白莲
首先，先找出中序遍历的序列，由后序遍历的特点可以知道最后一个结点G一定是根结点，观察A和B选项，发现A中的Z结点在 根的右边，而后序遍历结果中Z在M结点的前面，由于后序遍历是先遍历完左子树才遍历右子树，所以Z的位置不符合中序遍历的结果，A一定是错的所以选B，再根据B的中序序列就可以确定先序序列了。
发表于 2023-10-15 10:21:45 回复(0)
梁迪头像 梁迪
深度为 k 的满二叉树必有 2k-1 个节点，得出深度为4，然后填数
发表于 2020-02-20 22:19:32 回复(0)
直上云霄头像 直上云霄
由后序遍历知M一定是G的右孩子；故中序遍历一定是B；
而根据后序遍历知道E肯定是F的孩子，这对于前序遍历来说，E肯定在F的后面；而且后序遍历的最后一位G肯定是二叉树的根节点，放在前序遍历是第一位，综合比较四个选择，就是D
发表于 2019-11-14 09:38:52 回复(0)
March..头像 March..
只知道后序序列没法得到前序、中序序列。所以题目只能说是中序遍历可能 为 、后序遍历可能为  吧
发表于 2017-06-05 19:30:09 回复(0)
提交观点

问题信息

4399游戏 2017 前端工程师 树
来自：4399公司2017秋...
上传者：牛100
难度：
16条回答 7472浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号