Convert Sorted Array to Binary Search Tree -- LeetCode_leetcode convert sorted array to bst-程序员宅基地

技术标签：面试树 java 二分查找 leetcode LeetCode LeetCode总结

原题链接: http://oj.leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
这道题是二分查找树的题目，要把一个有序数组转换成一颗二分查找树。其实从本质来看，如果把一个数组看成一棵树（也就是以中点为根，左右为左右子树，依次下去）数组就等价于一个二分查找树。所以如果要构造这棵树，那就是把中间元素转化为根，然后递归构造左右子树。所以我们还是用二叉树递归的方法来实现，以根作为返回值，每层递归函数取中间元素，作为当前根和赋上结点值，然后左右结点接上左右区间的递归函数返回值。时间复杂度还是一次树遍历O(n)，总的空间复杂度是栈空间O(logn)加上结果的空间O(n)，额外空间是O(logn)，总体是O(n)。代码如下：

public TreeNode sortedArrayToBST(int[] num) {
    if(num==null || num.length==0)
        return null;
    return helper(num,0,num.length-1);
}
private TreeNode helper(int[] num, int l, int r)
{
    if(l>r)
        return null;
    int m = (l+r)/2;
    TreeNode root = new TreeNode(num[m]);
    root.left = helper(num,l,m-1);
    root.right = helper(num,m+1,r);
    return root;
}

这是一道不错的题目，模型简单，但是考察了遍历和二分查找树的数据结构，比较适合在电面中出现，类似的题目有 Convert Sorted List to Binary Search Tree ，是这道题非常好的后续问题，不同数据结构，实现上也会有所不同，有兴趣的朋友可以看看哈。

本文链接：https://blog.csdn.net/linhuanmars/article/details/23904883

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

PADS设置敷铜实心铜和网格铜_pads铺铜怎么是网格-程序员宅基地

文章浏览阅读2.7w次，点赞4次，收藏22次。PADS设置实心铜和网格铜有两个地方在控制，首先在layout界面中打开【工具】(Tool)->【选项】(Option)，找到【栅格和捕获】这一项，在右下侧有一个敷铜栅格，在这里输入1(该数字可为其他值，但是该值约小，敷铜能到达的区域越精确)，如下所示设置完该选项后，在敷铜的时候，双击敷铜的形状，然后出现特性界面，如下所示：然后将敷铜的线宽设置成和上面敷铜栅格一样的值，这里因为铺铜栅格是..._pads铺铜怎么是网格

【5G】CORESET解析-程序员宅基地

文章浏览阅读2.3k次，点赞4次，收藏28次。CORESET 结构介绍_coreset

基于java+ssm+vue的个人日程安排微信小程序_有日程管理的vue后台管理系统-程序员宅基地

文章浏览阅读104次。随着信息技术在管理上越来越深入而广泛的应用，管理信息系统的实施在技术上已逐步成熟。本文介绍了个人日程安排微信小程序的开发全过程。通过分析个人日程安排微信小程序管理的不足，创建了一个计算机管理个人日程安排微信小程序的方案。文章介绍了个人日程安排微信小程序的系统分析部分，包括可行性分析等，系统设计部分主要介绍了系统功能设计和数据库设计。本个人日程安排微信小程序管理员功能有个人中心，用户管理，重要日管理，工作日程管理，会面管理，用餐管理，日程管理，系统管理等。用户可以写自己的相关信息。因而具有一定的实用性。_有日程管理的vue后台管理系统

网关绑定命令,解决arp攻击-程序员宅基地

文章浏览阅读30次。一般家里的宽带都采用ADSL设备，通过固定IP地址接入Internet，但是经常会出现断网的现象，那么如何通过ARP命令绑定默认网关来解决这个问题呢？工具/原料ARP命令CMD命令提示符方法/步骤首先Win+R打开运行对话框，输入CMD。首先输入ipconfig/all命令并按回车键，查找默认网关的IP地址。然...

docker 银河麒麟镜像安装（随笔）_exec bin/docker-startup.sh: exec format error-程序员宅基地

文章浏览阅读1.4k次。1、由于是银河麒麟v10系统，拉下来得镜像安装时报错：exec bin/docker-startup.sh: exec format error 一直莫名其妙，找不到问题，后来在网上找到帖子说是因为镜像不支持这个系统，所以会报错，以mysql为例，之前的版本都只支持liunx/amd64,而银河麒麟系统基本都是liunx/arm64，所以安装失败。2.1、登录docker镜像仓库（_exec bin/docker-startup.sh: exec format error

跨镜追踪“智”眼识人技术策略研究及实现_跨境追踪人员监控系统-程序员宅基地

文章浏览阅读1.2k次。Labs 导读目前，在公共场景和个人应用场景中，监控摄像头安装总数已经超过了1.75亿，但大部分均为普通摄像头，通过监控录像实时存储和事件发生后调取查阅的方式被使用，它们缺少自主认知和决策的“大脑”，无法避免危险事件趋于恶化。在此背景下，具有智能视频行为分析功能的跨境追踪系统就显得尤为重要。本文将从跨镜追踪系统内部实现的角度展开论述，介绍跨镜追踪系统的核心功能及其应用场景。1、跨镜追踪技术背景跨镜追踪系统，主要利用行人重识别技术依据人物穿着、体态、发型等信息来判断图像或视频序列中是否存在特定的行_跨境追踪人员监控系统

随便推点

bootscrap-carousel_position, size, and scrollable content size are am-程序员宅基地

文章浏览阅读75次。carouselbootscrap直接看代码：<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="viewport" content="width=device-width, initial-scale=1._position, size, and scrollable content size are ambiguous for stackscrollabl