Question

某二叉树中序序列为A,B,C,D,E,F,G。后序序列为B,D,C,A,F,G,E,求前序

如题，希望把思路说一下

Answer 1

首先确定根结点,因为后序序列的最后为E,所以根节结点
然后在中序序列中把序列分成两部分,分别是ABCD和FG
分别把这两部分
在后序序列中找到
此时A为第一部分的最后
G为第二部分的最后
又中序序列为左中右
所以A为左孩子,G为右孩子
接下来
看A
显然A无左孩子
剩下的BCD
在后序序列中找
最后的为C
即A的右孩子为C
再看C
BCD
显然B为左孩子,D为右孩子
这样A子树就完了
再看G
显然左孩子为F
没有右孩子
所以前叙序列为EACBDGF