我要招人

去企业版

首页 > 试题广场 >

设某棵二叉树的中序遍历序列为BADC，前序遍历序列为ABCD

[单选题]

设某棵二叉树的中序遍历序列为BADC，前序遍历序列为ABCD，则后序遍历该二叉树得到序列为（）.

```
BADC
```
```
BDCA
```
```
BCDA
```
```
CBDA
```

查看答案及解析

老木子

中序遍历序列为BADC

前序遍历序列为ABCD

根为A

左子树为B

右子树为DC(中序)/CD(前序)

继续分解右子树，得到右子树根为C，结合DC和CD得出右子树的左孩子为D

（这里之前说错了，这里应该是左孩子，已更正 ）

（分析过程：CD是前序，根是C，DC是中序，在C前的只有可能是左孩子）

树为

B C

后序遍历为BDCA

编辑于 2016-09-01 16:52:43 回复(6)

伊利殺白

编辑于 2016-08-31 16:17:53 回复(7)

Jason_zhang

首先要确定是的遍历树的顺序：

前序：根左右

中序：左根右

后序：左右根

一般情况下，在知道了任意两种遍历的方式，就可以构造出一棵树。

构造树的技巧：比如找到了前序中的根节点，就可以在中序中确定根节点的位置，进而确定其左右的孩子位置。这样很容易构成一颗树

发表于 2016-09-11 14:57:18 回复(3)

Sakyaer

前/中/后序遍历指的是根节点相对于左右子节点的遍历顺序是1/2/3

发表于 2016-09-08 16:39:20 回复(0)

Blue_Smile

前序遍历：根节点-->左子树-->右子树

中序遍历：左子树 --> 根节点 ->右子树

后序遍历：左子树 ->右子树 --> 根节点

发表于 2016-10-09 23:04:40 回复(0)

勤修苦练

前序遍历第一个节点即为根节点，在中序遍历中找到相应元素，中序遍历两边分别为左右子树，之后递归找出所有子树位置

发表于 2016-08-30 13:44:56 回复(2)

舒意意123

BDCA

发表于 2017-04-05 20:15:22 回复(0)

贪I狼

前序遍历：根节点 --> 左子节点 --> 右子节点

中序遍历：左子节点 --> 根节点 --> 右子节点

后序遍历：左子节点 --> 右子节点 --> 根节点

根据二叉树的遍历方式，还原出该二叉树结构如下图：

根据后续遍历得结果为：BDCA

发表于 2017-03-09 23:49:38 回复(0)

小小哎呀

前序遍历：
    1.访问根节点
    2.前序遍历左子树
    3.前序遍历右子树
中序遍历：
    1.中序遍历左子树
    2.访问根节点
    3.中序遍历右子树
后序遍历：
    1.后序遍历左子树
    2.后序遍历右子树
    3.访问根节点

发表于 2017-02-04 16:22:44 回复(0)

蝶蝶恋花花

二叉树遍历:
    前序遍历：根节点 左子树 右子树
    中序遍历：左子树 跟结点 右子树
    后序遍历：左子树 右子树 根节点

编辑于 2016-12-06 15:48:53 回复(0)

牛客4174040号

根据前序和中序可知A是祖父节点，B C是父节点

发表于 2016-09-21 23:32:53 回复(0)

提交观点

问题信息

C++工程师网易有道 2017 树 Java工程师

来自：网易有道2017内推选择题

难度：

11条回答 327收藏 18058浏览

设某棵二叉树的中序遍历序列为BADC，前序遍历序列为ABCD

问题信息

热门推荐

相关试题