【剑指offer】问题7：重建二叉树

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

先上代码。

   /**
     * 重建二叉树
     */
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return core(pre, in, 0,pre.length - 1, 0, in.length - 1);
    }

    public TreeNode core(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd){
        // 根节点(前序遍历的第一个节点)
        int rootVal = pre[preStart];
        TreeNode root = new TreeNode(rootVal);
        // 找到根节点在中序遍历数组中的位置
        int rootIndexIn = inStart;
        for(;rootIndexIn <= inEnd; rootIndexIn++){
            if(in[rootIndexIn] == rootVal)
                break;
        }
        // 计算左子树的长度
        int leftLen = rootIndexIn - inStart;
        // 计算右子树的长度
        int rightLen = inEnd - rootIndexIn;
        if(leftLen > 0){
            // 存在左子树
            // 找到左子树的中序遍历数组
            int leftInStart = inStart;
            int leftInEnd = leftInStart + leftLen - 1;
            // 找到左子树的前序遍历数组
            int leftPreStart = preStart + 1;
            int leftPreEnd = leftPreStart + leftLen - 1;
            // 构建左子树
            root.left = core(pre,in,leftPreStart, leftPreEnd, leftInStart, leftInEnd);
        }

        if(rightLen > 0){
            // 存在右子树
            // 找到右子树的中序遍历数组
            int rightInStart = rootIndexIn + 1;
            int rightInEnd = rightInStart + rightLen - 1;

            // 找到右子树的前序遍历数组
            int rightPreStart = preEnd - rightLen + 1;
            int rightPreEnd = preEnd;

            // 构建右子树
            root.right = core(pre, in, rightPreStart, rightPreEnd, rightInStart, rightInEnd);
        }

        return root;
    }

关于树的问题很多都可以使用递归的方式解决，只要将一般化的处理过程想清楚，再把返回条件搞好，基本就可以。本题已知二叉树的前序遍历和中序遍历结果，找出根节点的值，然后再根据这个值找出左子树和右子树对应的前序和中序遍历结果，就可以进行递归编程了。此题比较麻烦的子树数组的界限问题，处理好这个问题，递归也就不会出错了。
详细的解题流程在注释里已经比较清楚，不再赘述。