首页 > 试题广场 >

已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DB

[填空题]
已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为1
查看正确选项
添加回答
红萝卜头像 红萝卜
发表于 2015-08-24 10:53:14 回复(1)
南山北头像 南山北
前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
发表于 2016-08-10 14:50:52 回复(0)
高腾龙头像 高腾龙

发表于 2016-04-28 10:36:27 回复(2)
Aesthetic92头像 Aesthetic92
答案： DGEBHFCA
后序遍历是：如果一个结点有左孩子或者右孩子，则先遍历左孩子和右孩子，然后再遍历根结点，所以这题后序遍历是 DGEBHFCA
发表于 2015-01-13 01:23:03 回复(0)
SunShine11头像 SunShine11
1、前序遍历的第一个节点为根节点，由题中前序遍历可知，A为根节点；
2、中序遍历的根节点前面的节点均为左子树的节点，所以左子树上的节点为DBGE；
3、去掉根节点和左子树节点，右子数节点为CHF；
4、前序遍历的第二个节点为B，由2知B为左子树节点，所以B为左子树的根节点；
5、由前序遍历，DEG在B节点的下面，由中序遍历可知，D是B的左节点，GE是B的右节点；
6、由前序遍历，E是G的根节点，由中序遍历，G是E的左子节点；
7、由前序遍历，C是二叉树的右根节点，由中序遍历，C不含左子节点，HF均为C的右子节点；
8、由前序遍历，F为H的根节点，由中序遍历，H为F的左子节点。
综上可知，二叉树形状如下图：




发表于 2016-08-23 10:48:45 回复(0)
da阿福头像 da阿福
前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
想到一个取巧的办法：后序的第1个=中序的第1个；后序遍历的最后1个=前序的最后1个
然后BCD都排除了。。。

发表于 2019-08-23 21:07:53 回复(0)
思不如学头像 思不如学
失误失误 看反了。。。。
发表于 2016-03-24 13:10:22 回复(0)
百度高级测试开发工程师头像 百度高级测试开发工程师
是我失误了
发表于 2016-03-09 21:24:57 回复(0)
予我深拥头像 予我深拥
首先利用先序和中序画出树，然后做。
发表于 2016-03-07 17:28:05 回复(0)
牛客331538号头像 牛客331538号
不懂
发表于 2015-08-01 18:21:46 回复(0)
提交观点

问题信息

树
上传者：聚丙烯
难度：
10条回答 18539浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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