Question

二叉树遍历题

某二叉树前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则后序遍历的结点访问顺序是多少？
怎么推算的？

Answer 1

后序序列为gdbehfca

过程是首先还原二叉树，再求出后序遍历序列，过程如下：

首先从前序第一个得到根，回到中序来将其分割为左子树dgb、根a、右子树echf

再分别按照左右子树的结点回到各自的前序来再次求出左右子树的根，依然是回到刚才已经切分出左右子树的中序序列来分割

重复这个过程，就可以还原出二叉树了

问题的二叉树如下：

追问

再想问下，为什么d在左边，g在右边，而且g是连接的d而没有连接b？

追答

从前序确定了根以后，在中序中切分，根后面的就是右子树

Answer 2