108. 将有序数组转换为二叉搜索树【简单】

108. 将有序数组转换为二叉搜索树【简单】


题目描述:

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1:
在这里插入图片描述

输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:

在这里插入图片描述

示例 2:
在这里插入图片描述

输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3][3,1] 都是高度平衡二叉搜索树。

提示

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 按 严格递增 顺序排列

JAVA代码:

(一)递归方法

设定中间位置为根节点(可以自己设定哪个作为根节点,所以有很多种的结果),选择中间作为根节点可以保证高度平衡。
递归思路
选择中间位置所谓根节点,那么左边所有的数字都小于它,作为左子树。右边所有的数字都大于它,作为右子树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return help(nums,0,nums.length-1);
    }
    public TreeNode help(int[] nums,int left,int right){
        if(left>right) return null;
        int mid = (left+right)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = help(nums,left,mid-1);
        root.right = help(nums,mid+1,right);
        return root;
    }
}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/429314.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

电脑不小心格式化了,怎么恢复?

在这个数字化时代&#xff0c;电脑已经成为我们日常生活和工作中不可或缺的工具。然而&#xff0c;有时我们可能会不小心格式化电脑硬盘&#xff0c;导致重要数据的丢失。那么&#xff0c;电脑不小心格式化了&#xff0c;怎么恢复&#xff1f; 别着急&#xff0c;在本篇攻略中&…

vue3页面内容切换(类似登录、注册内容切换)

一、内容描述 页面有俩块内容&#xff0c;分别是验证码登录页面内容&#xff0c;账号密码登录页面内容。有俩种处理方式&#xff0c;一个是写俩个页面跳转使用&#xff0c;还有一种是一个页面俩个内容&#xff0c;切换的只是不同的内容&#xff0c;相同的内容保留。一般都是选择…

音视频开发之旅——音频基础概念、交叉编译原理和实践(LAME的交叉编译)(Android)

本文主要讲解的是音频基础概念、交叉编译原理和实践&#xff08;LAME的交叉编译&#xff09;&#xff0c;是基于Android平台&#xff0c;示例代码如下所示&#xff1a; AndroidAudioDemo 音频基础概念 在进行音频开发的之前&#xff0c;了解声学的基础还是很有必要的。 声音…

Windows安装SSH教程

Windows安装SSH教程 一、SSH1.SSH简介2.SSH功能3.SSH验证3.1 第一种级别&#xff08;基于口令的安全验证&#xff09;3.2 第二种级别&#xff08;基于密匙的安全验证&#xff09; 4.SSH层次4.1 传输层协议 [SSH-TRANS]4.2 用户认证协议 [SSH-USERAUTH]4.3 连接协议 [SSH-CONNEC…

改造muduo,不依赖boost,用C++11重构

组件的实现 1. 序 1.1. 总述 muduo库是基于多Reactor-多线程模型实现的TCP网络编程库&#xff0c;性能良好。如libev作者&#xff1a;“One loop per thread is usually a good model”&#xff0c;muduo库的作者陈硕在其《Linux多线程服务端编程》中也力荐这种“One loop pe…

linux中对信号的认识

信号的概念与相关知识认识 信号是向目标进程发送消息通知的的一种机制。 信号可以以异步的方式发送给进程&#xff0c;也就是说&#xff0c;进程无需主动等待&#xff0c;而是在任何时间都可以接收到信号。 信号的种类 用kill-l命令查看系统定义的信号列表&#xff1a; 前台…

初识Hive

官网地址为&#xff1a; Design - Apache Hive - Apache Software Foundation 一、架构 先来看下官网给的图&#xff1a; 图上显示了Hive的主要组件及其与Hadoop的交互。Hive的主要组件有&#xff1a; UI&#xff1a; 用户向系统提交查询和其他操作的用户界面。截至2011年&…

Linux - 安装 maven(详细教程)

目录 一、下载二、安装三、配置环境变量四、镜像资源配置 一、下载 官网&#xff1a;https://maven.apache.org/download.cgi 打开 maven 的官网下载页面&#xff0c;点击 bin.tar.gz 文件链接 即可下载最新版本的 maven 如果想要下载旧版本的 meven&#xff0c;则点击 Maven…

【短时交通流量预测】基于GRNN神经网络

课题名称&#xff1a;基于GRNN神经网络的短时交通流量预测 版本时间&#xff1a;2023-04-27 代码获取方式&#xff1a;QQ&#xff1a;491052175 或者 私聊博主获取 模型简介&#xff1a; 城市交通路网中交通路段上某时刻的交通流量与本路段前几个时段的交通流量有关&#x…

Python类 __init__() 是一个特殊的方法

设计者&#xff1a;ISDF工软未来 版本&#xff1a;v1.0 日期&#xff1a;2024/3/5__init__() 是一个特殊的方法 类似c# C的构造函数 两头都包含两个下划线&#xff0c;这是约定&#xff0c;用于与普通的函数保持区分class User:用户类def __init__(self,first_name,last_name):…

软件应用,财务收支系统试用版操作教程,佳易王记录账单的软件系统

软件应用&#xff0c;财务收支系统试用版操作教程&#xff0c;佳易王记录账单的软件系统 一、前言 以下软件操作教程以 佳易王账单记账统计管理系统V17.0为例说明 软件文件下载可以点击最下方官网卡片——软件下载——试用版软件下载 如上图&#xff0c;统计报表包含 收支汇…

JavaScript基础2之运算符、函数

JavaScript基础 运算符一元操作符递增/递减一元加和减 布尔操作符逻辑非逻辑与逻辑或 乘性操作符乘法操作符除法操作符取模操作符 加性操作符加法操作符减法操作符 比较操作符相等操作符关系操作符 函数函数声明函数表达式箭头函数函数的实参和形参arguments 默认参数参数的拓展…

QUIC来了!

什么是QUIC QUIC&#xff0c;快速UDP网络连接(Quick UDP Internet Connection)的简称&#xff0c;即RFC文档描述它为一个面向连接的安全通用传输协议。其基于UDP协议实现了可靠传输及拥塞控制&#xff0c;简单来说&#xff0c;QUIC TCP TLS。 为什么有了QUIC HTTP2.0为了为了…

如何处理微服务之间的通信和数据一致性?

✨✨祝屏幕前的兄弟姐妹们每天都有好运相伴左右&#xff0c;一定要天天开心哦&#xff01;✨✨ &#x1f388;&#x1f388;作者主页&#xff1a; 喔的嘛呀&#x1f388;&#x1f388; 目录 引言 一、微服务通信 1、同步通信&#xff1a;HTTP 1.1.同步通信示例代码&#xf…

第四十九回 吴学究双掌连环计 宋公明三打祝家庄-Python与HTTP服务交互

吴用请戴宗从梁山请来铁面孔目裴宣、圣手书生萧让、通臂猿侯健、玉臂匠金大坚来帮忙。又告诫扈家庄的扈成&#xff0c;打起来不要去帮祝家庄。 孙立把旗号改成“登州兵马提辖孙立”&#xff0c;来祝家庄找峦廷玉&#xff0c;被热情接待。 第三天&#xff0c;宋江派小李广花荣…

Vue 路由功能

安装路由 npm install vue-router4创建路由器并导出 //导入vue-router import { createRouter, createWebHistory } from vue-router //导入组件 import LoginVue from /views/Login.vue import LayoutVue from /views/Layout.vue//定义路由关系 const routes [{ path: /log…

安卓玩机工具推荐----ADB状态读写分区 备份分区 恢复分区 查看分区号 工具操作解析

在以往玩机过程中。很多机型备份分区 备份固件需要借助adb手动指令或者第三方手机软件或者特定的一些工具来操作。有些朋友需要查看当前机型分区名称和对应的分区号。此类操作我前面的博文专门说过对应的adb指令。但有些界面化的工具比较方便简单。 相关分区同类博文&#xff…

WPF中如何设置自定义控件(二)

前一篇文章中简要讲解了圆角按钮、圆形按钮的使用,以及在windows.resource和app.resource中设置圆角或圆形按钮的样式。 这篇主要讲解Polygon(多边形)、Ellipse(椭圆)、Path(路径)这三个内容。 Polygon 我们先看一下的源码: namespace System.Windows.Shapes { pu…

性能问题分析排查思路之机器(3)

本文是性能问题分析排查思路的展开内容之一&#xff0c;第2篇&#xff0c;主要分为日志1期&#xff0c;机器4期、环境2期共7篇系列文章&#xff0c;本期是第三篇&#xff0c;讲机器&#xff08;硬件&#xff09;的网络方面的排查方法和最佳实践。 主要内容如图所示&#xff1a…

【短时交通流量预测】基于单层BP神经网络

课题名称&#xff1a;基于单层BP神经网络的短时交通流量预测 版本时间&#xff1a;2023-04-27 代码获取方式&#xff1a;QQ&#xff1a;491052175 或者 私聊博主获取 模型简介&#xff1a; 城市交通路网中交通路段上某时刻的交通流量与本路段前几个时段的交通流量有关&…