剑指Offer:面试题6——重建二叉树（java实现）

问题描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不包含重复的数字。

例如：

输入：前序{1,2,4,7,3,5,6,8}，中序{4,7,2,1,5,3,8}

输出：相应的树根结点

思路1：递归。

前序遍历：根（左子树）（右子树）

中序遍历：（左子树）根（右子树）

先从前序遍历剥出 根结点

然后从中序遍历中剥出：左子树和右子树，递归建立子树，并与根结点的左右指针链接。

public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre == null || in == null || pre.length == 0 || in.length == 0){
            return null;
        }
        if(pre.length == 1 && in.length == 1){
            return new TreeNode(pre[0]);
        }
        int root = pre[0];
        TreeNode tree = new TreeNode(root);        int del = -1;
        for(int i = 0; i < in.length;i++){
            if(in[i] == root){
                del = i;
                break;
            }
        }
        int right_length = in.length - del - 1;
        int[] left_pre = new int[del];
        int[] left_in = new int[del];
        int[] right_pre = new int[right_length];
        int[] right_in = new int[right_length];        for(int i = 1; i < del+1; i++){
            left_pre[i-1] = pre[i];
            left_in[i-1] = in[i-1];
        }
        for(int i = del+1; i < pre.length; i++){
            right_pre[i - del - 1] = pre[i];
            right_in[i - del - 1] = in[i];
        }        tree.left = reConstructBinaryTree(left_pre, left_in);
        tree.right = reConstructBinaryTree(right_pre, right_in);        return tree;    }