Question

某二叉树的前根次序列遍历结果为stuwv，中序遍历为uwtvs，则该二叉树的后序是什么？如何画图？

Answer 1

对于先序遍历stuwv, 和中序遍历uwtvs可以这么分析：

规则：
1）先序遍历确定父节点
2）中序遍历确定左右子树
分析过程：
1、由前序遍历可知s为树的根
s
tuwv
2、结合中序遍历可知：tuwv为s左子树的先序遍历， uwtv为s左子树的中序遍历
3、同理判断t为左子树的根,uw为t的左子树， v为t的右子树
s
t
uw v
4、递归判断t的左子树可知： 其先序遍历和中序遍历均为uw，判断u为子树的根节点，w为u的右孩子
s
/
t
/ \
u v
\
w
由此可知其后序遍历为：wuvts