某二叉树的中序序列为 BDCA ，后序序列为 DCBA ，则

[单选题]

某二叉树的中序序列为 BDCA ，后序序列为 DCBA ，则前序序列是（）。

```
DCBA
```
```
BDCA
```
```
ABCD
```
```
BADC
```

查看答案及解析

P-ShineBeam

发表于 2020-02-13 10:50:37 回复(0)

更多回答

main方法栈帧

根据题目提供的条件
基本可以确定A是该二叉树的根节点
原因是后序遍历最后1个元素是A

再根据中序遍历最后一个元素是A
可以判断A没有右子树(root.rightNode = null)

然后根据B的遍历位置
可以判断B要么在A的左子树，并且B没有左子节点
要么B是A左子树的左子树，并且B没有左子节点
原因是B在中序遍历时排在第1位

由于后续遍历B没有在第1位
可以排除第2种情况
所以B是A的左子节点
并且B没有左子树

然后就是C和D了
此时CD排列有４种情况
可以1个1个带入看看那个答案是对的

这里可以看出不管是中序还是后续
D都在C的前面
所以D绝对是C的左子节点
至于为什么就懒得说了

所以最终答案是
A
/
B
\
C
/
D

编辑于 2021-11-11 19:21:31 回复(0)

赞花婆

【解析】二叉树遍历可以分为 3 种：前序遍历（访问根结点在访问左子树和访问右子树之前）、中序遍历（访问根结点在访问左子树和访问右子树两者之间）、后序遍历（访问根结点在访问左子树和访问右子树之后）。本题中中序序列为 BDCA ，后序序列为 DCBA, 可知 A 为根结点， BDC 为左侧结点， C 是 B 右子结点， D 是 C 右子结点，故前序序列为 ABCD ， C 选项正确。

发表于 2017-05-02 20:15:03 回复(1)