最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

经典面试题35_最小高度树解法思路

XAMPP相关 admin 612浏览 0评论

来源:LeetCode

难度:简单

描述:

给定一个有序整数数组,元素各不相同且按升序排列,编写一个算法,创建一棵高度最小的二叉搜索树。

示例1:

给定有序数组: [-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:
0
/    \
-3         9
/         /
-10        5 

分析:

题目给的是个有序数组,并且是要构成二叉搜索树。二叉搜索树的特点就是根节点大于左节点,小于右节点。

既然是要构成深度最小的数,那么树就应该尽可能的饱满。所以我们每次就选择数组的中间点作为根节,这样左边和右边都是同样的大小,构成的树自然就是最饱满的,深度亦是最小的

 

解题

方法一:二分法

思路:

如分析,每次利用二分法找到数组的中间,将数组一分为二,中间节点作为根节点,左边的序列为左子树,右边的序列为右子树。再利用递归构建左右子树即可

代码:

 1public TreeNode sortedArrayToBST(int[] nums) {
 2    if (nums == null || nums.length == 0) {
 3        return null;
 4    }
 5    return buildBST(nums, 0, nums.length - 1);
 6}
 7
 8private TreeNode buildBST(int[] nums, int start, int end) {
 9    if (start > end) {
10        return null;
11    }
12    //找到中间位置
13    int mid = (start + end) / 2;
14    //中间节点最为根节点
15    TreeNode root = new TreeNode(nums[mid]);
16    //中间节点左边为左子树
17    root.left = buildBST(nums, start, mid - 1);
18    //中间节点右边为右子树
19    root.right = buildBST(nums, mid + 1, end);
20    return root;
21}

时间复杂度:O(n) n为数组元素个数

空间复杂度:O(logn) 二分法递归,使用了辅助栈

 

以上仅是个人思路解法

转载请注明:XAMPP中文组官网 » 经典面试题35_最小高度树解法思路

您必须 登录 才能发表评论!