一棵二叉树的先序遍历序列为A,B,C,D,E,F,中序遍历序

[单选题]

一棵二叉树的先序遍历序列为A,B,C,D,E,F,中序遍历序列为C,B,A,E,D,F，则后序遍历序列为：

查看正确选项

凌201904252009410

先知道什么是先序、中序、后序遍历

先序遍历：根、左、右

中序遍历：左、根、右

后序遍历：左、右、根

这里先序是A,B,C,D,E,F，所以根是A；中序遍历序列为C,B,A,E,D,F，所以C,B在根节点A的左侧，D,E,F在右侧；

然后我们先来确定A左侧的结构：

A左侧只有B和C。根据先序，可以知道B是根；根据中序可以知道C是B的左孩子。

然后是A右侧的结构：

A右侧是D,E,F。根据先序，可以知道D是根；

那么E是D的左孩子还是右孩子呢？根据中序可知E一定是D的左孩子；

根据中序，F在D的右侧，所以它只能是D的右孩子，不可能是E的左/右孩子

树形结构如图

发表于 2019-05-15 21:09:45 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师前端工程师 PHP工程师携程 2019 Java工程师

上传者：小小

难度：

1条回答 37收藏 3749浏览

扫一扫，把题目装进口袋