已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是? A acbed

Question

已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是?
A acbed B decab C deabc Dcedba
希望得到详细点的解答，我在此谢过了。

Answer 1

选D。
由后序遍历可知c是根结点，符合条件的只有D。追问

但是怎么判断出原来的二叉树是什么样子呢？

追答

也可以的，步骤如下：
1、由后续遍历可知c是根结点。
2、由中序遍历可知deba在c的左孩子树上。
3、由后序遍历知e是c的左孩子树的根结点。
4、由中序遍历可知d是e的左孩子，ba在e的右孩子树上。
5、由后序遍历，可以得出b是e的右孩子，a是e的左孩子，而第4步中确定了a不在e的左孩子数上，因此，a只能在b上。
6、由中序遍历，可知，a是b的右孩子。
可以得出原二叉树如下图：

追问

太感谢你了！谢谢，我会好好努力的