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

LeetCode 算法:将有序数组转换为二叉搜索树 c++

原题链接🔗:将有序数组转换为二叉搜索树
难度:简单⭐️

题目

给你一个整数数组 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 按 严格递增 顺序排列

平衡二叉搜索树

  • 平衡二叉搜索树(Balanced Binary Search Tree,简称BBST)是一种特殊的二叉搜索树,它在保持二叉搜索树的所有性质的同时,还保证了树的高度尽可能地小。这通常通过在插入和删除操作后重新平衡树来实现,以确保树的任何两个子树的高度差不会超过1。

  • 平衡二叉搜索树的一个常见实现是AVL树,它是一种自平衡的二叉搜索树,其名称来源于其发明者Adelson-Velsky和Landis。AVL树在每次插入或删除操作后,都会进行必要的旋转操作来保持树的平衡。

  • AVL树的平衡操作包括四种基本的旋转:

    • 左旋(Left Rotation):当节点的右子树比左子树高时,进行左旋来减少树的高度。
    • 右旋(Right Rotation):当节点的左子树比右子树高时,进行右旋来减少树的高度。
    • 左右旋(Left-Right Rotation):当节点的左子树的右子树比左子树高时,首先对左子树进行右旋,然后对节点进行左旋。
    • 右左旋(Right-Left Rotation):当节点的右子树的左子树比右子树高时,首先对右子树进行左旋,然后对节点进行右旋。
  • AVL树的每个节点除了存储值和指向左右子节点的指针外,还存储了一个平衡因子(balance factor),通常是左子树高度和右子树高度的差值。节点的平衡因子只能是-1、0或1。

题解

递归法

  1. 解题思路

将一个有序数组转换为二叉搜索树(BST)的解题思路基于二叉搜索树的性质:左子树上所有节点的值 < 根节点的值 < 右子树上所有节点的值。对于一个有序数组,我们可以利用数组的有序性来快速确定根节点和左右子树的划分点。

以下是解题步骤:

  • 确定根节点:对于有序数组,中间元素(数组长度的一半)是一个很好的根节点候选,因为它可以很好地维持左右子树的大小平衡。

  • 递归构建左右子树:使用数组下标来划分,左子树包含从数组开始到根节点前的部分,右子树包含从根节点的下一个元素到数组末尾的部分。

  • 递归终止条件:当子数组为空时,返回null。

  • 构建树:对于每个子数组,重复上述步骤,递归地构建左右子树。

  • 返回根节点:递归结束时,返回构建的树的根节点。

下面是具体的算法逻辑:

  • 定义一个递归函数sortedArrayToBST,它接收有序数组的起始索引和结束索引作为参数。
  • 计算中间索引mid:mid = (start+ end) / 2
  • 使用mid索引处的值创建一个新的树节点。
  • 递归地调用sortedArrayToBST来构建左子树,使用start和mid - 1作为新的参数。
  • 递归地调用sortedArrayToBST来构建右子树,使用mid + 1和end作为新的参数。
  • 将左子树和右子树分别赋值给新创建的根节点的左右子节点。
  • 返回根节点。
  1. 复杂度:时间复杂度O(n),空间复杂度O(logn)。

  2. c++ demo

#include <iostream>
#include <vector>// 定义二叉树节点
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 将有序数组转换为二叉搜索树的函数
class Solution {
public:TreeNode* sortedArrayToBST(std::vector<int>& nums) {return sortedArrayToBSTHelper(nums, 0, nums.size() - 1);}private:TreeNode* sortedArrayToBSTHelper(std::vector<int>& nums, int start, int end) {if (start > end) {return nullptr;}// 选择中间的元素作为根节点int mid = start + (end - start) / 2;TreeNode* node = new TreeNode(nums[mid]);// 递归地构建左子树和右子树node->left = sortedArrayToBSTHelper(nums, start, mid - 1);node->right = sortedArrayToBSTHelper(nums, mid + 1, end);return node;}
};// 辅助函数:中序遍历二叉树并打印节点值
void inorderTraversal(TreeNode* node) {if (!node) return;inorderTraversal(node->left);std::cout << node->val << " ";inorderTraversal(node->right);
}// 辅助函数:释放二叉树内存
void deleteTree(TreeNode* node) {if (!node) return;deleteTree(node->left);deleteTree(node->right);delete node;
}int main() {// 创建Solution实例Solution solution;// 有序数组std::vector<int> nums = { -10, -3, 0, 5, 9 };// 将有序数组转换为BSTTreeNode* root = solution.sortedArrayToBST(nums);// 中序遍历BST并打印节点值std::cout << "Inorder traversal of the constructed BST:" << std::endl;inorderTraversal(root);std::cout << std::endl;// 释放二叉树内存deleteTree(root);return 0;
}
  • 输出结果:

Inorder traversal of the constructed BST:
-10 -3 0 5 9

  1. demo 仓库地址:sortedArrayToBST

相关文章:

LeetCode 算法:将有序数组转换为二叉搜索树 c++

原题链接&#x1f517;&#xff1a;将有序数组转换为二叉搜索树 难度&#xff1a;简单⭐️ 题目 给你一个整数数组 nums &#xff0c;其中元素已经按 升序 排列&#xff0c;请你将其转换为一棵 平衡 二叉搜索树。 示例 1&#xff1a; 输入&#xff1a;nums [-10,-3,0,5,9]…...

智慧公厕系统改变了人们对服务区公厕的看法

在过去&#xff0c;服务区公厕常常给人留下脏乱差的印象&#xff0c;成为人们在长途旅行途中不愿停留的地方。然而&#xff0c;随着智慧科技的不断发展和应用&#xff0c;智慧公厕系统的出现改变了人们对服务区公厕的看法&#xff0c;为公共卫生设施的提升注入了新的活力。 一、…...

终极指南:RNNS、Transformers 和 Diffusion 模型

一、说明 作为广泛使用这些工具和模型的人&#xff0c;我的目标是解开 RNN、Transformer 和 Diffusion 模型的复杂性和细微差别&#xff0c;为您提供详细的比较&#xff0c;为您的特定需求提供正确的选择。 无论您是在构建语言翻译系统、生成高保真图像&#xff0c;还是处理时间…...

WPF UI 3D 基本概念 点线三角面 相机对象 材质对象与贴图 3D地球 光源 变形处理 动作交互 辅助交互插件 系列三

WPF UI交互专题 平面图形 Path Drawing 绘图 渐变 Brush 矩阵 Transform 变形 阴影效果 模糊效果 自定义灰度去色效果 系列二-CSDN博客 1软件中的3D基本概念 WPF 中 3D 功能的设计初衷并非提供功能齐全的游戏开发平台。 WPF 中的 3D 图形内容封装在 Viewport3D 元素中&#x…...

分子AI预测赛Task2笔记

下面所述比较官方的内容都来自官方文档 ‍‌⁠‌‍​​​‌​​⁠​​​​​&#xfeff;​​​&#xfeff;‍‬​​‍⁠‍‍​​‬​&#xfeff;‌​​​‌‍‬​​​​​​‍‌Task2&#xff1a;赛题深入解析 - 飞书云文档 (feishu.cn) 赛题背景 强调了人工智能在科研领域&…...

剖析DeFi交易产品之UniswapV4:创建池子

本文首发于公众号&#xff1a;Keegan小钢 创建池子的底层函数是 PoolManager 合约的 initialize 函数&#xff0c;其代码实现并不复杂&#xff0c;如下所示&#xff1a; function initialize(PoolKey memory key, uint160 sqrtPriceX96, bytes calldata hookData)externalover…...

速盾:cdn内容分发服务有哪些优势?

CDN&#xff08;Content Delivery Network&#xff09;是指内容分发网络&#xff0c;是一种将网络内容分发到全球各个地点的技术和架构。在现代互联网架构中&#xff0c;CDN已经变得非常重要。CDN通过将内容分发到靠近用户的服务器上&#xff0c;提供高速、高效的服务。下面是C…...

如何利用React和Python构建强大的网络爬虫应用

如何利用React和Python构建强大的网络爬虫应用 引言&#xff1a; 网络爬虫是一种自动化程序&#xff0c;用于通过互联网抓取网页数据。随着互联网的不断发展和数据的爆炸式增长&#xff0c;网络爬虫越来越受欢迎。本文将介绍如何利用React和Python这两种流行的技术&#xff0c…...

炎黄数智人:招商局集团推出AI数字员工“招小影”

引言 在全球数字化浪潮的推动下&#xff0c;招商局集团开启了一项具有里程碑意义的项目。招商局集团将引入AI数字员工“招小影”&#xff0c;这一举措不仅彰显了招商局集团在智能化转型方面的坚定决心&#xff0c;也为企业管理模式的创新注入了新的活力。 “招小影”是一款集成…...

【开发篇】明明配置跨域声明,为什么却仍可以发送HTTP请求

一、问题 在SpringBoot项目中&#xff0c;明确指定仅允许指定网站跨域访问&#xff1a; 为什么开发人员却仍旧可以通过HTTP工具调用接口&#xff1f; 二、为什么 在回答这个问题之前&#xff0c;我们首先要了解一下什么是CORS&#xff01; 1、什么是CORS CORS的全称为跨域资源…...

单片机中有FLASH为啥还需要EEROM?

在开始前刚好我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「单片机的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&#xff01; 一是EEPROM操作简单&…...

Qt的源码目录集合(V5.12.12版本)

目录 1.QObject实现源码 2.qml中的ListModel实现源码 3.qml中的JS运行时的环境和数据类型源码 1.QObject实现源码 .\Qt\Qt5.12.12\5.12.12\Src\qtbase\src\corelib\kernel\qobject.h .\Qt\Qt5.12.12\5.12.12\Src\qtbase\src\corelib\kernel\qobject.cpp .\Qt\Qt5.12.12\5…...

记因hive配置文件参数运用不当导致 sqoop MySQL导入数据到hive 失败的案例

sqoop MySQL导入数据到hive报错 ERROR tool.ImportTool: Encountered IOException running import job: java.io.IOException: Hive exited with status 64 报错解释&#xff1a; 这个错误表明Sqoop在尝试导入数据到Hive时遇到了问题&#xff0c;导致Hive进程异常退出。状态码…...

自动化邮件通知:批处理脚本的通讯增强

自动化邮件通知&#xff1a;批处理脚本的通讯增强 引言 批处理脚本在自动化任务中扮演着重要角色&#xff0c;无论是在系统管理、数据处理还是日常任务调度中。然而&#xff0c;批处理脚本的自动化能力可以通过集成邮件通知功能得到显著增强。当脚本执行完毕或在执行过程中遇…...

236、二叉树的最近公共祖先

前提&#xff1a; 所有 Node.val 互不相同 。p ! qp 和 q 均存在于给定的二叉树中。 代码如下&#xff1a; class Solution { public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root q || root p || root NULL) return root;TreeN…...

WebStorm 2024 for Mac JavaScript前端开发工具

Mac分享吧 文章目录 效果一、下载软件二、开始安装1、双击运行软件&#xff08;适合自己的M芯片版或Intel芯片版&#xff09;&#xff0c;将其从左侧拖入右侧文件夹中&#xff0c;等待安装完毕2、应用程序显示软件图标&#xff0c;表示安装成功3、打开访达&#xff0c;点击【文…...

【Redis7】零基础篇

1 课程概述 2 Redis入门概述 2.1 是什么 Redis是基于内存的KV键值对内存数据库 Redis&#xff1a;Remote Dictionary Server(远程字典服务)是完全开源的&#xff0c;使用ANSIC语言编写遵守BSD协议&#xff0c;是一个高性能的Key-Value数据库提供了丰富的数据结构&#xff0c…...

[ROS 系列学习教程] 建模与仿真 - 使用 ros_control 控制差速轮式机器人

ROS 系列学习教程(总目录) 本文目录 一、差速轮式机器人二、差速驱动机器人运动学模型三、对外接口3.1 输入接口3.2 输出接口 四、控制器参数五、配置控制器参数六、编写硬件抽象接口七、控制机器人移动八、源码 ros_control 提供了多种控制器&#xff0c;其中 diff_drive_cont…...

Ubuntu22.04使用Systemd设置ROS 2开机自启动遇到的问题

在查找网上的各种开机自启动资料配置好开机自启动后&#xff0c;使用ros2 topic list不能显示话题。 1、问题解决&#xff1a;用户问题与domenID问题2、ROS2开机自启动服务教程3、多个ROS2开机自启动服务教程 1、问题解决&#xff1a;用户问题与domenID问题 在root用户下能看到…...

AI安全研究滞后?清华专家团来支招

在21世纪的科技浪潮中&#xff0c;人工智能&#xff08;AI&#xff09;无疑是最为耀眼的一抹亮色。随着技术的不断突破&#xff0c;AI正以前所未有的速度融入我们的日常生活&#xff0c;重塑着社会、经济乃至人类文明的面貌。然而&#xff0c;在这股汹涌澎湃的发展洪流中&#…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

《Docker》架构

文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器&#xff0c;docker&#xff0c;镜像&#xff0c;k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter

java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用&#xff08;Math::max&#xff09; 2 函数接口…...