这是我做的一个版本，速度会慢些，因为在递归里面有一个数组的copy
public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder == null || preorder.length == 0) return null; TreeNode root = new TreeNode(-1); rebuild(root, preorder, inorder, root); return root; } public void rebuild(TreeNode node, int[] preorder, int[] inorder, TreeNode root){ if (!(preorder.length == 0 || inorder.length == 0)){ //获取先序的第一个数 int rootVal = preorder[0]; //获取该数字在中序中的位置 int inPos = 0; for (int i=0; i<inorder.length; i++){ if (inorder[i] == rootVal){ inPos = i; } } //左边和右边数组 int[] preorderLeft = Arrays.copyOfRange(preorder, 1, inPos+1); int[] preorderRight = Arrays.copyOfRange(preorder, inPos+1, preorder.length); int[] inorderLeft = Arrays.copyOfRange(inorder, 0, inPos); int[] inorderRight = Arrays.copyOfRange(inorder, inPos+1, inorder.length); node.val = rootVal; if (preorderLeft.length != 0){ node.left = new TreeNode(-1); rebuild(node.left, preorderLeft, inorderLeft, root); } if (preorderRight.length != 0 ){ node.right = new TreeNode(-1); rebuild(node.right, preorderRight, inorderRight, root); } }else{ node = null; } }
修改版，用treeNode作为返回值
还可以进一步优化，不适用Arrays.copyRange而使用游标来标记位置
public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder == null || preorder.length == 0) return null; return rebuild(preorder, inorder); } public TreeNode rebuild(int[] preorder, int[] inorder){ if (!(preorder.length == 0 || inorder.length == 0)){ //获取先序的第一个数 int rootVal = preorder[0]; //获取该数字在中序中的位置 int inPos = 0; for (int i=0; i<inorder.length; i++){ if (inorder[i] == rootVal){ inPos = i; } } //左边和右边数组 int[] preorderLeft = Arrays.copyOfRange(preorder, 1, inPos+1); int[] preorderRight = Arrays.copyOfRange(preorder, inPos+1, preorder.length); int[] inorderLeft = Arrays.copyOfRange(inorder, 0, inPos); int[] inorderRight = Arrays.copyOfRange(inorder, inPos+1, inorder.length); TreeNode node = new TreeNode(rootVal); node.left = rebuild(preorderLeft, inorderLeft); node.right = rebuild(preorderRight, inorderRight); return node; }else{ return null; } }