Question

已知二叉树前序、中序遍历结果，求后序遍历结果？

Answer 1

例：若某二叉树的前遍历访问顺序是序abdgcefh,中序遍历顺序是dgbaechf
（1）由前序遍历结果我们可知a为根结点，再看中序遍历结果，因为中序遍历顺序是左子树、根、右子树，因此由“中序遍历顺序是dgbaechf”可断定，dgb为该二叉树的左子树中序遍历结果，echf为右子树中序遍历结果。
（2）由前序遍历结果可知，左子树的前序遍历结果是bdg,右子树的前序遍历结果是cefh;因此，和第一步分析类似，可知b为左子树的根，再由“dgb为该二叉树的左子树中序遍历结果”可知，dg为该左子树的左子树的中序遍历结果，再由dg在前序遍历结果中排列顺序dg可知，d为根，因此由“dg为该左子树的左子树的中序遍历结果”可推出g为d的右孩子。
到此为止，可以完全推断出该二叉树的左子树的结构了。
按照同样方法，可以推断出该二叉树的右子树的结构，因此整个二叉树的结构图如下：
据此图，不难看出该二叉树的后序遍历结果是：gdbehfca.