已知二叉树的中序序列为DBEAFC，后序序列为DEBFCA，

[单选题]

已知二叉树的中序序列为DBEAFC，后序序列为DEBFCA，请问其前序序列为（）

```
ABDECF
```
```
ABDCEF
```
```
BDEFCA
```
```
BDFECA
```

查看正确选项

牛客235893896号

中序遍历顺序是左根右得到DBEAFC,后序遍历顺序是左右根得到DEBFCA，所以由后序遍历结果可知A是整个树的根节点，再由中序的DBE和后序的DEB可推出，B是A左边子树的根节点，D是B左边的子节点，E是B右边的子节点。再由中序的AFC和后序的FCA可以推出，C是A右边子树的根节点，F是C左边的子节点，再根据根节点→左子树→右子树的顺序进行前序遍历即可得到答案。

发表于 2021-01-26 16:04:12 回复(0)