[二叉树] 从前序与中序遍历序列构建二叉树

• 给定一棵树的前序遍历 preorder 与中序遍历 inorder，然后构造二叉树并返回其根节点。

    public int preIndex = 0;
    public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend) {
        if(inbegin > inend)
            return null;

        //1.依次取前序遍历的第一个数，构造根结点
        TreeNode root = new TreeNode(preorder[preIndex]);

        //2.然后去中序遍历中寻找该结点，其左为二叉树的左子树结点，其右为二叉树的右子树结点
        int rootIndex = findIndexOfInorder(inorder, inbegin, inend, preorder[preIndex]);
        preIndex++;  //更新前序遍历序列的第一个结点
        if(rootIndex == -1)
            return null;

        //3.依次建立root的左子树和右子树
        root.left = buildTreeChild(preorder, inorder, inbegin, rootIndex-1);
        root.right = buildTreeChild(preorder, inorder, rootIndex+1, inend);

        return root;
    }

    public int findIndexOfInorder(int[] inorder, int inbegin, int inend, int val){
        for(int i=inbegin; i<=inend; i++){
            if(inorder[i] == val)
                return i;
        }
        return -1;  //没有在中序遍历序列中找到该结点
    }


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null || inorder==null)
            return null;
        if(preorder.length<=0 || inorder.length<=0)
            return null;
        return buildTreeChild(preorder, inorder, 0, inorder.length-1);
    }