首页 > 试题广场 >

一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可

[单选题]
一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（） 
  • CABDEFG
  • ABCDEFG
  • DACEFBG
  • ADCFEG
查看正确选项
添加回答
菜鸟201711052124359头像 菜鸟201711052124359
第一种方法：硬算，把每个答案都代入一遍，如果出现矛盾的话，结果不正确。

第二种：转化成入栈出栈问题。
1.一棵二叉树的前序遍历结果，就是前序遍历时候元素入栈顺序。
2.一颗二叉树的中序、后序遍历的结果，就是中序遍历、后序遍历遍历时候元素出栈顺序。
所以这个问题就变成了，如果给定一个栈，入栈顺序是ABCDEFG，那么下面哪种出栈顺序是不可能的。
我们来看看D选项。 
DBCEAFG
如果D要第一个出栈，那么我们就必须：
  • 把ABCD按顺序压入栈，然后D作为栈顶元素出栈。
  • 然后我们看看第二个出栈元素是B，这时候栈里面还有ABC，栈顶是C，所以无论如何都无法让B出栈。矛盾。所以D选项错误。
发表于 2020-03-31 15:54:43 回复(4)
luffy-xiong头像 luffy-xiong
当二叉树所有节点都只有有右孩子时，B成立！
发表于 2015-09-02 08:55:49 回复(1)
Vricky头像 Vricky
之前忘了从哪看到，只要将前序入栈，然后判断中序是不是他的出栈顺序就好，啥原因我忘了。。
发表于 2017-05-08 18:21:57 回复(4)
Johndan头像 Johndan
依据先序遍历找到每个中序遍历序列的分割点，保证分割点左右两边所有的元素在先序遍历中也呈现先左后右边的顺序， 例如C项中DACEFBG被Ａ分割为D（左） CEFBG（右），那么则先序中的D必然在CEFBG之前，依次类推!
编辑于 2016-07-21 09:16:34 回复(1)
啥头像 啥
看给定的前序和选项中的中序能否构成一颗二叉树，按照平常重构步骤来，有矛盾就不行
发表于 2016-01-26 09:03:17 回复(0)
牛客585229243号头像 牛客585229243号
通过前序遍历序列为ABCDEFG得知根节点为A，中序遍历的规则是左根右。
假设此二叉树有左子树，即可能为DBC或CBD开头所以排除A和C选项；
假设此二叉树无左子树，通过左根右顺序得知右子树必然和前序遍历的右子树相同，即排除D选项，所以正确为B
编辑于 2022-12-06 17:02:53 回复(0)
Bertking头像 Bertking
快速解题技巧：栈的出栈顺序
发表于 2020-11-26 19:46:51 回复(1)
Iam乙太头像 Iam乙太
就看到了只有有孩子的时候B项是对的就选了
发表于 2023-04-21 11:24:29 回复(0)
kktb头像 kktb
这道题选b，先通过栈将前序序列对得到的ABCDEFG按续一次排入栈，根据选项取元素，除B以外都不符合
发表于 2019-10-23 20:06:58 回复(0)
7秒記憶_47692头像 7秒記憶_47692
只知道前序遍历的顺序，中序遍历是不确定的
发表于 2015-08-25 11:13:38 回复(0)
eagle头像 eagle
B
发表于 2015-01-08 00:18:39 回复(0)
提交观点

问题信息

树
难度：
11条回答 19151浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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