[数据结构与算法]重建二叉树

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

题目中给出了二叉树的先序遍历和中序遍历，我们知道二叉树的先序遍历的顺序是：中左右
所以给定的先序遍历数组的第一个数值一定是整个二叉树的根节点
二叉树中序遍历的顺序是：左中右
知道了根节点之后，我们在中序遍历中找到根节点对应的下标，在下标的左边就是这个根节点的左子树，右边就是这个根节点的右子树

 public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0){
            return null;
        }
        int inorderRootIndex = -1;
        // 根据前序遍历的根节点，在中序遍历中找到
        for(int i = 0 ;i<inorder.length;i++){
            if(inorder[i] == preorder[0]){
                inorderRootIndex = i;
            }
        }
        // 计算出左子树长度
        int leftNum = inorderRootIndex;
        int rightNum = inorder.length - leftNum - 1;
		// 构建一个新节点，准备递归连接
        TreeNode treeNode = new TreeNode(preorder[0]);
        // 递归连接子树，处理下字符串长度
        // subString的区间是左闭右开，(n,k)取的是[n,k-1]下标的元素
        treeNode.left = buildTree(Arrays.copyOfRange(preorder, 1, leftNum + 1), Arrays.copyOfRange(inorder, 0,leftNum));
        treeNode.right = buildTree(Arrays.copyOfRange(preorder, 1 + leftNum, preorder.length),Arrays.copyOfRange(inorder, leftNum+1, preorder.length));
        return treeNode;
    }