错误解法一：preorder[0]为根节点，在inorder中找到preorder[0]的位置numInorder，其左边为左子树，右边为右子树。利用Arrays.copyOfRange()函数来取数组子集。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder.length==0){return null;}// 找到preorder[0]在inoder中的位置int numInoger;for(numInoger=0;numInoger<inorder.length;numInoger++){if(preorder[0]==inorder[numInoger]){break;}}int[] newPreorder = Arrays.copyOfRange(preorder,1,preorder.length);int[] newInoderLeft = Arrays.copyOfRange(inorder,0,numInoger);int[] newInoderRight = Arrays.copyOfRange(inorder,numInoger+1,inorder.length);TreeNode left = buildTree(newPreorder, newInoderLeft);TreeNode right = buildTree(newPreorder, newInoderRight);return new TreeNode(preorder[0], left, right);}
}

错误原因：

int[] newInoderRight = Arrays.copyOfRange(inorder,numInoger+1,inorder.length)：Arrays.copyOfRange()无法处理numInoger+1==inorder.length的情况。

解法一：由解法二发现的问题改进上述错误解法 =》速度慢！！！！

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder.length==0){return null;}// 找到preorder[0]在inoder中的位置int numInoger;for(numInoger=0;numInoger<inorder.length;numInoger++){if(preorder[0]==inorder[numInoger]){break;}}// 得到左子树中的节点数目int num_left = numInoger;int[] newPreorderLeft = Arrays.copyOfRange(preorder,1,1+numInoger);int[] newPreorderRight = Arrays.copyOfRange(preorder,1+numInoger,preorder.length);int[] newInoderLeft = Arrays.copyOfRange(inorder,0,numInoger);int[] newInoderRight = Arrays.copyOfRange(inorder,numInoger+1,inorder.length);TreeNode left = buildTree(newPreorderLeft, newInoderLeft);TreeNode right = buildTree(newPreorderRight, newInoderRight);return new TreeNode(preorder[0], left, right);}
}

解法二：preorder[0]为根节点，在inorder中找到preorder[0]的位置numInorder，其左边为左子树，右边为右子树。利用双指针函数来取数组子集。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);}public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right){if(preorder_left>preorder_right){return null;}// 找到preorder[preorder_left]在inoder中的位置int numInoger;for(numInoger=inorder_left;numInoger<=inorder_right;numInoger++){if(preorder[preorder_left]==inorder[numInoger]){break;}}TreeNode root = new TreeNode(preorder[preorder_left]);// 得到左子树中的节点数目int num_left = numInoger - inorder_left;root.left = myBuildTree(preorder, inorder, preorder_left+1, preorder_left+num_left, inorder_left, numInoger-1);root.right = myBuildTree(preorder, inorder,preorder_left+num_left+1, preorder_right, numInoger+1, inorder_right);return root;}
}

注意：

• 不能使用TreeNode left = myBuildTree(preorder, inorder, preorder_left+1, preorder_right, inorder_left, numInoger-1)和TreeNode right = myBuildTree(preorder, inorder, preorder_left+1, preorder_right, numInoger+1, inorder_right)，递归的不是preorder余下的所有数，而是要区分余下的数哪些在左子树+哪些在右子数：利用左子树中的节点数目num_left = numInoger - inorder_left来确定
• 速度慢 =》改进：构造哈希映射，帮助我们快速定位根节点HashMap(inorder[i], i)