当前位置: 首页 > news >正文

力扣每日一题108:将有序数组转换为二叉搜索树

题目

简单

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 

平衡

 二叉搜索树。

示例 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 <= 104
  • -104 <= nums[i] <= 104
  • nums 按 严格递增 顺序排列

面试中遇到过这道题?

1/5

通过次数

471.9K

提交次数

601.7K

通过率

78.4%

思路

平衡二叉搜索树有两个要求

1、每个节点左右子树的高度差不能超过1

2、每个节点的大于所有左子树结点,小于所有右子树结点。

要满足第一个条件的话,我们可以递归建树,每次将中间的值作为根节点,然后递归调用左右两部分。

要满足第二个条件,只需将root->left指向左边部分递归的结果,root->right指向右边部分递归的结果即可。

代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode *creat(int lo,int hi,vector<int>& nums){if(lo>hi) return NULL;int mid=(lo+hi)/2;TreeNode *root=new TreeNode;root->val=nums[mid];root->left=creat(lo,mid-1,nums);root->right=creat(mid+1,hi,nums);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {int lo=0,hi=nums.size()-1;TreeNode *root=creat(lo,hi,nums);return root;}
};

http://www.lryc.cn/news/343456.html

相关文章:

  • 保护公司机密:避免员工带着数据说拜拜
  • kali apt update报错
  • 7-1 图图图
  • Java(多线程)
  • 程序员必备的7大神器,效率飞起!
  • 揭秘文件加密利器:24年度最值得信赖的5大加密软件评测
  • 【仪酷LabVIEW AI工具包案例】使用LabVIEW AI工具包+YOLOv5结合Dobot机械臂实现智能垃圾分类
  • 鸿蒙应用开发系列 EX篇:HarmonyOS应用开发者基础认证
  • 基于Linux中的 进程相关知识 综合讲解
  • 前端高频面试题 5.08
  • python 的继承、封装和多态
  • 数智结合,智慧合同让法务管理发挥内在价值
  • Ubuntu 安装docker
  • 【北京迅为】《iTOP-3588开发板快速烧写手册》-第8章 TF启动
  • Helm 模板流程控制
  • Kansformer?变形金刚来自过去的新敌人
  • 今晚 19:00 | 从这两个问题入手,带你了解数据要素相关税务问题
  • 《QT实用小工具·五十一》带动画的 CheckBox
  • PDT(police digital trunking )警用数字集群射频指标及测试方法
  • 《尿不湿级》STM32 F103C8T6最小系统板搭建(五)BOOT
  • Java项目:基于SSM框架实现的高校专业信息管理系统设计与实现(ssm+B/S架构+源码+数据库+毕业论文+PPT+开题报告)
  • linux高性能服务器-线程池实现
  • 算法训练营第56天|LeetCode 583.两个字符串的删除操作 72.编辑距离
  • 首页最新 多IP浏览器防关联:如何配置多个独立且稳定的IP地址?
  • 电脑连接公司打印机教程
  • JavaScript 中的 Promise.all
  • 机器视觉_联合编程(二)
  • AUTOCRAWLER : A Progressive Understanding Web Agent for WebCrawler Generation
  • php使用服务器端和客户端加密狗环境部署及使用记录(服务器端windows环境下部署、linux环境宝塔面板部署、客户端部署加密狗)
  • Android selinux权限