已知二叉树的前序遍历和中序遍历，如何得到它的后序遍历？

在前文数据结构：二叉树的原理及java实现中，我们已经了解了二叉树的原理及二叉树的三种遍历方式，假设父节点是N，左节点是L，右节点是R：

前序遍历 N－>L－>R
中序遍历 L－>N－>R
后序遍历 L－>R－>N

对于下面的二叉树，遍历结果分别为

前序遍历：ABDECF
中序遍历：DBEACF
后序遍历：DEBFCA

已知二叉树的前序遍历和中序遍历，如何得到它的后序遍历

其实，只要知道其中任意两种遍历的顺序，我们就可以推断出剩下的一种遍历方式的顺序，这里我们只是以：知道前序遍历和中序遍历，推断后序遍历作为例子，其他组合方式原理是一样的。要完成这个任务，我们首先要利用以下几个特性：

特性A，对于前序遍历，第一个肯定是根节点；
特性B，对于后序遍历，最后一个肯定是根节点；
特性C，利用前序或后序遍历，确定根节点，在中序遍历中，根节点的两边就可以分出左子树和右子树；
特性D，对左子树和右子树分别做前面3点的分析和拆分，相当于做递归，我们就可以重建出完整的二叉树；

我们以一个例子做一下这个过程，假设：

前序遍历的顺序是: CABGHEDF
中序遍历的顺序是: GHBACDEF

我们根据特性A，可以得知根节点是C，然后，根据特性C，我们知道左子树是：GHBA，右子树是：DEF。

        C
     /     \
GHBA   DEF

取出左子树，左子树的前序遍历是：ABGH，中序遍历是：GHBA，根据特性A和C，得出左子树的父节点是A，并且A没有右子树。

        C
      /    \
     A    DEF
    /
GBH

使用同样的方法，前序是BGH，中序是GHB，得出父节点是B，G和H分别是左右节点。

回到右子树，它的前序是EDF，中序是DEF，依然根据特性A和C，得出父节点是E，左右节点是D和F。

             C
         /        \
        A           E
      /           /    \
     B           D      F
   /    \
G      H

到此，我们得到了这棵完整的二叉树，因此，它的后序遍历就是：GHBADFEC。

程序实现

下面我们使用程序来实现根据前序遍历和中序遍历得到后续遍历。
首先我们需要建立节点的实体类

/**
 * 二叉树的节点数据结构
 */
public class TreeNode {
    private String key = null;
    private String data = null;
    public boolean isVisted = false;
    /**
     * 左儿子节点
     */
    public TreeNode leftChild = null;
    /**
     * 右儿子节点
     */
    public TreeNode rightChild = null;

    /**
     * 默认构造方法
     */
    public TreeNode(){}

    /**
     * @param key  层序编码
     * @param data 数据域
     */
    public TreeNode(String key, String data){
        this.setKey(key);
        this.setData(data);
        this.leftChild = null;
        this.rightChild = null;
    }

    /**
     * 序号
     */
    public String getKey() {
        return key;
    }

    public void setKey(String key) {
        this.key = key;
    }

    /**
     * 值
     */
    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }
}