回顾一下二叉树的三种遍历
只要峩们知道中序和先序或着后序 那么我们就可以根据已知的两种遍历序列
求出剩下的另一种遍历序列
例:已知该二叉树的先序遍历序列为:A-B-D-E-G-C-F中序遍历序列为:D-B-G-E-A-C-F。求该二叉树后序遍历序列
第一步:找根 先序遍历先遍历根结点 那么它的序列第一个肯定是根节点也就是上面的A
第二步:找根结点的左右子数 中序遍历先左后根后右 在中序序列中找到根结点的位置那么它的左边就是它的左子树序列 右边就是它的右子数序列
第三步:拆分转化为子问题 去掉A结点 将树分为两个二叉树 B-D-E-G 和C-F
然后按照第一步分别找两颗树的根 B C 然后根据第二部找根的左右子数
最后我们僦可以根据后续遍历规则得出该二叉树的后续遍历序列为:D-G-E-B-F-C-A