前序:先遍历根节点,再遍历左孩子,最后遍历右孩子
中序:先遍历左孩子(以中序遍历),再遍历根节点,最后遍历右孩子(以中序遍历)
后序:先遍历左孩子(以后序遍历)再遍历右孩子(以后序遍历),最后遍历根节点
本题:有前序得到根节点:A,有中序得到左孩子:DBC,右孩子:FEG,再有前序或中序得出树的结构
最后得出后序遍历的结果:DCBFGEA
题目的先序印错了,根据题目的先序是不可能产生这样的中序的。
先序是先根再左子树再右子树,中序是先左子树再根节点最后右子树,后序是先左子树再右子树最后根节点。
中序是二叉树的水平投影,再根据先或后序可以得到二叉树的
A
B E
D C F G
DBCAFEG 中序
答案的后序是 DCBFGEA
可验证我的二叉树是正确的
则先序是ABDCEFG