每日一题算法：2020年7月3日 将有序数组转换为二叉搜索树 sortedArrayToBST

2020年7月3日 将有序数组转换为二叉搜索树 sortedArrayToBST

默认格式：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode sortedArrayToBST(int[] nums) { } }

解题思路：

首先，我们要知道什么是一个二叉搜索树，去百度截个图

简单来说，就是为了方便我们查找数组中的某一个元素，而构建的一种数据结构。

例如，我们有一个数组[1,2,3,4,5,6,8,11,23,42,44,54]这一个数组，我们要找一个数字需要多少次，最少1次，最多12次，平均6.5次。

而如果我们构建一颗搜索二叉树。

搜索一个数最多使用4次。

这就是搜索二叉树的好处。

那么怎么做一个高度平衡的二叉树呢？

使用二分法，平均分开两边的个数，这样就能做到平衡二叉树。

实现代码：

今天的题目简单的逻辑没有什么好说的，不过有一点需要注意，对于裁剪一个数组的操作来说，使用System.arraycopy这个方法是最优的。

这个方法是直接通过地址复制数组，而不是像Arrays那样靠循环来给数组赋值。

总之，如果你需要复制一个数组，尽量使用这个方法，这个方法比较快

public TreeNode sortedArrayToBST(int[] nums) { if (nums.length==0) return null; int len=nums.length; int val=nums[len/2]; TreeNode root=new TreeNode(val); int[] newNums1=new int[len/2]; int[] newNums2=new int[(len-1)/2]; System.arraycopy(nums,0 ,newNums1 ,0 , len/2); System.arraycopy(nums,len/2+1 ,newNums2 ,0 , (len-1)/2); root.left=sortedArrayToBST(newNums1); root.right=sortedArrayToBST(newNums2); return root; }