根据先序遍历和后续遍历重构二叉树

今天在牛客网上遇到这样一道题，题目内容如下：

题目描述:
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

题目的意思是根据一棵二叉树的先序和后续序列重构二叉树。
阶梯思路是：
（1）首先先序中的第一个元素一定是二叉树的根节点。根据这个根节点找到在中序中的位置，那么这一位置左边的元素全部是二叉树的左孩子，这一节点的所有右边节点全部是二叉树的右孩子。
（2）其次构造右子树和左子树。构造思路是：从先序和中序中找到左子树和右子树的先序和中序序列，然后递归构造，直至所有节点使用完。即得到重构的二叉树。

参考代码如下：

//节点的数据结构
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
public class Main {
    public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if(pre.length == 0 || in.length == 0 || pre.length != in.length){
            return null;
        }
        //在中序中找到根节点所在的位置，中序中该位置左边的为左子树，右边的为右子树
        int i = 0;
        while(pre[0] != in[i]){
            i++;
        }
        //创建一棵树
        TreeNode root = new TreeNode(pre[0]);
        //左子树中序为
        int inLeftTree[] = new int[i];
        for(int k = 0; k < i ; k++){
            inLeftTree[k] = in[k];
        }
        //右子树中序为
        int inRightTree[] = new int[in.length - i -1];
        for(int k = i + 1; k < in.length; k++){
            inRightTree[k - i -1] = in[k];
        }
        //左子树的先序为
        int preLeft[] = new int[i];
        for(int k = 0; k < i; k++){
            preLeft[k] = pre[k + 1];
        }
        //右子树的先序为
        int preRight[] = new int[pre.length - i - 1];
        for(int k = i + 1; k < pre.length; k++){
            preRight[k -i -1] = pre[k];
        }
        //递归构造左右子树
        root.left = reConstructBinaryTree(preLeft, inLeftTree);
        root.right = reConstructBinaryTree(preRight, inRightTree);
        return root;
    }

    public static void main(String[] args) {
        int[] a = { 1, 2, 4, 7, 3, 5, 6, 8 };
        int[] b = { 4, 7, 2, 1, 5, 3, 8, 6 };
        TreeNode root = reConstructBinaryTree(a, b);

        //后续遍历二叉树
        lastList(root);
    }
    //后续遍历这棵二叉树 以验证重构的是否正确
    private static void lastList(TreeNode root) {
        if(root == null){
            return;
        }
        last(root.left);
        last(root.right);
        System.out.print(root.val + " ");
    }
}

转发连接：http://blog.csdn.net/a469142780/article/details/76222341

这二叉树的实际结构如下图：