已知二叉树的前序、中序遍历，求二叉树的后序遍历

1.二叉树的深度优先遍历

二叉树的深度优先遍历有三种形式，分别是：

前序遍历：遍历顺序为根左右；

中序遍历：遍历顺序为左根右；

后序遍历：遍历顺序为左右根。

以下面一颗二叉树为例，它的不同形式的深度优先遍历的结果为：

前序遍历：1 2 4 7 3 5 6 8

中序遍历：4 7 2 1 5 3 8 6

后序遍历：7 4 2 5 8 6 3 1

2.已知二叉树的前序、中序遍历，求二叉树的后序遍历

        当我们已知一颗二叉树的前序、中序遍历，或者是中序、后序遍历的结果时，可以重建出该二叉树，而已知前序、后序遍历则无法重建。因此，想要根据二叉树的前序、中序遍历，求得它的后序遍历，只需先将二叉树重建出来，再对其进行后序遍历即可。

        问题的关键在于如何根据二叉树的前序、中序遍历重建出二叉树。这里继续以上文的二叉树为例，它的前序遍历为：1 2 4 7 3 5 6 8、中序遍历为：4 7 2 1 5 3 8 6。注意前序遍历的顺序为根左右，因此它的第一个元素（1）即为二叉树的根结点。知道根结点后，在中序遍历的结果中找到它的位置，中序遍历的顺序为左根右，因此在它左侧的结点即为根结点的左子树，在它右侧的结点即为根结点的右子树，对于子树再进行相同的分析即可。完整过程示例如下：

1为根结点，在中序遍历中左侧节点有：4 7 2，为它的左子树、右侧结点有：5 3 8 6，为它的右子树；

对于根结点的左子树4 7 2，前序遍历顺序为2 4 7，因此它的根结点为2，左子树为4 7，无右子树；

对于左子树4 7，前序遍历顺序为4 7，因此它的根结点为4，无左子树，右子树为7；

对于右子树7，它无左右子树，是叶子结点。

对于根结点的右子树5 3 8 6，前序遍历顺序为3 5 6 8，因此它的根结点为3，左子树为5，右子树为8 6；

对于左子树5，它无左右子树，是叶子结点；

对于右子树8 6，前序遍历顺序为6 8，因此它的根结点为6，左子树为8，无右子树；

对于左子树8，它无左右子树，是叶子结点。

利用递归的思路将以上过程用代码实现，示例如下（利用ArrayList比数组更加方便）：

public static TreeNode solve(ArrayList pre, ArrayList vin){
        if(pre.isEmpty()) return null;
        //得到根结点
        int val = pre.get(0);
        TreeNode root = new TreeNode(val);
        //寻找根结点在中序遍历中的位置
        int index = vin.indexOf(val);
        //它左侧的为左子树
        ArrayList l_pre = new ArrayList<>(pre.subList(1,index+1));
        ArrayList l_vin = new ArrayList<>(vin.subList(0,index));
        root.left = solve(l_pre, l_vin);
        //它右侧的为右子树
        ArrayList r_pre = new ArrayList<>(pre.subList(index+1,pre.size()));
        ArrayList r_vin = new ArrayList<>(vin.subList(index+1,pre.size()));
        root.right = solve(r_pre, r_vin);
        return root;
}

得到二叉树后，再对其进行后序遍历 ：

public static String last_dfs(TreeNode root,StringBuilder s) {
    	if(root.left!=null)	last_dfs(root.left,s);
		if(root.right!=null) last_dfs(root.right,s);
        //最终输出时用trim()方法去除多余的空格
		return s.append(root.val+" ").toString();
}