首页 > 试题广场 >

使用中序遍历一棵二叉树得到E A C K F H D B G

[单选题]
使用中序遍历一棵二叉树得到E A C K F H D B G，使用后序遍历得到E C K A H B G D F，则先序遍历将得到（） 
  • FAEKCDBHG
  • FAEKCDHGB
  • EAFKHDCBG
  • FEAKDCHBG
查看正确选项
添加回答
黄小辉€柒小曦头像 黄小辉€柒小曦
B 后序遍历最后一个节点是根节点，在结合中序遍历，得知EACK是根节点F的左边节点，HDBG是根节点的右边节点，由于后序遍历是先遍历左节点、右节点，最后遍历根节点，中序遍历是先左节点、根节点，再右节点就可以判断F的右节点是D，D的左节点是H，G是D的右节点，B是G的左节点。由于中序遍历和后序遍历都是以E开头，得知E一定是左节点，而且处于最底层，再根据中序遍历和后序遍历的特点就可以完整的推断出这个二叉树的分布。
发表于 2018-05-22 16:50:00 回复(0)
可留头像 可留
前序遍历：先遍历根节点，接着遍历左子树，最后遍历右子树
中序遍历：先遍历左子树，接着遍历根节点，最后遍历右子树
后序遍历：先遍历左子树，接着遍历右子树，最后遍历根节点
注意每一次遍历都要严格执行以上步骤
由后续遍历可以确定最上方的根节点为F,然后以中序遍历可以确定EACK为F的左子树，HDBG为F的右子树；
对比中序遍历和后序遍历的前四个字目，容易发现，最左子树为E，E的根节点为A，CK为A的右子树，严格按照定义，可知C为K的左子树
同理，观察F的右子树，易知D为根节点，H为D左子树，GB为右子树，G为B的根节点
请严格按定义遍历！！！！

发表于 2018-05-29 21:20:06 回复(0)
牛客9548317号头像 牛客9548317号
由后序遍历可以推导这个二叉树正中间的节点为F，然后根据中序和后续都是由E开始，可以确定E节点一定是在最坐标，而且是最左边，然后根据后序遍历可以看出A后面的为H，因此可以推导H也在最左边，在由二叉树的遍历规则可以很快推出答案。
发表于 2018-05-22 15:28:45 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 京东 2018 PHP工程师 Java工程师
上传者：小小
难度：
3条回答 3256浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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