首页 > 试题广场 >

若某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是DB

[单选题]
若某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是DBCAFGE，则该二叉树的后序遍历序列是 
  • DBCFGEA
  • CDBGFEA
  • GFCDEBA
  • DCBGFEA
查看正确选项
添加回答
有芝士的海头像 有芝士的海
这道题我的解题思路是这样的： 从中序遍历和前序遍历当中我们可以迅速得出A是一个根节点，由此可知，BCD和EFG分别是左右子树。那进一步细分，我们就可以得到一棵树，左子树就是B是根节点，D是左子树，C是右子树。 右子树，则E是根节点，注意，这里F是E的左子树，G是F的右子树。由此就可以得到D答案了。 图片不知道上传，只能用文字描述了。
发表于 2021-10-08 08:01:58 回复(0)
Decade_头像 Decade_
这题的前序遍历应该是ABDCEFG吧....

发表于 2021-08-25 16:02:19 回复(2)
pein531头像 pein531
这个题的左子树很迷啊，怎么都不对
发表于 2021-09-03 17:17:59 回复(2)
牛也可波罗头像 牛也可波罗
我觉得题目错了...
发表于 2022-04-18 15:58:22 回复(0)
牛客953500800号头像 牛客953500800号
①由前序遍历 得到A为二叉树的根节点
②中序遍历为 左子树 根节点 右子树，所以A左边的DBC为二叉树的左子树  FGE为右子树
③由前序遍历BCD得到 B为CD的父节点 再结合中序遍历DBC
综上 可以得到二叉树的左边部分为
后序遍历顺序为 左右根 由上图得出后序遍历前半部分为DCB 至此答案选D

继续分析下去 可得整颗二叉树 如图

发表于 2021-09-02 22:01:55 回复(1)
牛客294806047号头像 牛客294806047号
错题
发表于 2023-10-08 15:44:01 回复(0)
牛客544976319号头像 牛客544976319号
这题没答案吧，矛盾着呢

发表于 2021-08-30 18:41:39 回复(0)
提交观点

问题信息

微众银行 运维工程师 测试开发工程师 测试工程师 安全工程师 2021 Java工程师
上传者：小小
难度：
7条回答 1228浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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