• 软件:1160
  • 资讯:41601|
  • 收录网站:97880|

IT精英团

510,将有序数组转换为二叉搜索树

510,将有序数组转换为二叉搜索树

浏览次数:
评论次数:
编辑: 温瑜
信息来源: 51CTO博客
更新日期: 2021-06-13 00:19:02
摘要

510,将有序数组转换为二叉搜索树, Opportunitydoesnotknock,itpresentsitselfwhenyoubeatdownthedoor.  机遇不会自己找上门来,它只会在你开门时出现。问题描述将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。 示例: 给定有序

  • 资讯详情

Opportunity does not knock, it presents itself when you beat down the door.   

机遇不会自己找上门来,它只会在你开门时出现。

问题描述

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:

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

递归方式解决

题中说了要转换为一棵高度平衡的二叉搜索树,并且数组又是排过序的,这就好办了。


我们可以使用递归的方式,每次取数组中间的值比如m作为当前节点,m前面的值都是比他小的,作为他左子树的结点值。m后面的值都是比他大的,作为他右子树的节点值,示例中一个可能的结果是。

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

代码如下

 1public TreeNode sortedArrayToBST(int[] num) {
2    //边界条件判断
3    if (num.length == 0)
4        return null;
5    return sortedArrayToBST(num, 0, num.length - 1);
6}
7
8//start表示数组开始的位置,end表示的结束的位置
9public TreeNode sortedArrayToBST(int[] num, int start, int end) {
10    if (start > end)
11        return null;
12    int mid = (start + end) >> 1;
13    //取中间值作为当前节点
14    TreeNode root = new TreeNode(num[mid]);
15    //然后递归的方式,中间值之前的是当前节点左子树的所有节点
16    root.left = sortedArrayToBST(num, start, mid - 1);
17    //中间值之后的是当前节点的右子树的所有节点
18    root.right = sortedArrayToBST(num, mid + 1, end);
19    return root;
20}

总结

之前讲过466. 使用快慢指针把有序链表转换二叉搜索树,和这题非常类似,只不过第466题是链表,这里改为了数组,更简单了。

509,数组中的第K个最大元素
« 上一篇
返回列表
下一篇 »
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
你会是第一个来这里评论的人吗?
最近发布资讯
更多