189.二叉树:将有序数组转换为二叉搜索树(力扣)

2024-06-21 14:44

本文主要是介绍189.二叉树:将有序数组转换为二叉搜索树(力扣),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

代码解决

/*** 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:// 辅助函数,用于递归地构建BSTTreeNode* traversal(vector<int>& nums, int left, int right){// 如果左边界大于右边界,返回空节点if (left > right) return nullptr;// 取数组的中间元素作为根节点int mid = (left + right) / 2;TreeNode* root = new TreeNode(nums[mid]);// 递归构建左子树root->left = traversal(nums, left, mid - 1);// 递归构建右子树root->right = traversal(nums, mid + 1, right);return root;}// 主函数,将排序数组转换成BSTTreeNode* sortedArrayToBST(vector<int>& nums) {// 初始化左边界和右边界int left = 0;int right = nums.size() - 1;// 调用辅助函数构建BSTTreeNode* root = traversal(nums, left, right);return root;}
};

代码使用了递归的方法。主要思路是首先找到数组的中间元素,然后以这个中间元素作为根节点,递归地在数组中构建左右子树。左子树包含数组中所有小于中间元素的元素,右子树包含所有大于中间元素的元素。

这里简要解释一下代码的工作流程:

  1. 定义一个辅助函数 traversal,它接受一个排序数组、左边界和右边界作为参数。
  2. 如果左边界大于右边界,返回空节点。
  3. 找到数组的中间元素,并以这个元素作为当前节点的值。
  4. 递归地构建左子树,左子树的元素值应小于当前节点的值,左边界为 left,右边界为 mid - 1
  5. 递归地构建右子树,右子树的元素值应大于当前节点的值,左边界为 mid + 1,右边界为 right
  6. 返回构建好的根节点。
  7. 在 sortedArrayToBST 函数中,初始化左边界和右边界,然后调用 traversal 函数构建二叉搜索树。

这个算法的时间复杂度是 O(n),其中 n 是数组中元素的数量。空间复杂度也是 O(n),因为需要存储递归调用的栈。

这篇关于189.二叉树:将有序数组转换为二叉搜索树(力扣)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1081512

相关文章

Java对象转换的实现方式汇总

《Java对象转换的实现方式汇总》:本文主要介绍Java对象转换的多种实现方式,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Java对象转换的多种实现方式1. 手动映射(Manual Mapping)2. Builder模式3. 工具类辅助映

python实现svg图片转换为png和gif

《python实现svg图片转换为png和gif》这篇文章主要为大家详细介绍了python如何实现将svg图片格式转换为png和gif,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录python实现svg图片转换为png和gifpython实现图片格式之间的相互转换延展:基于Py

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C#实现将Excel表格转换为图片(JPG/ PNG)

《C#实现将Excel表格转换为图片(JPG/PNG)》Excel表格可能会因为不同设备或字体缺失等问题,导致格式错乱或数据显示异常,转换为图片后,能确保数据的排版等保持一致,下面我们看看如何使用C... 目录通过C# 转换Excel工作表到图片通过C# 转换指定单元格区域到图片知识扩展C# 将 Excel

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

使用Python开发一个带EPUB转换功能的Markdown编辑器

《使用Python开发一个带EPUB转换功能的Markdown编辑器》Markdown因其简单易用和强大的格式支持,成为了写作者、开发者及内容创作者的首选格式,本文将通过Python开发一个Markd... 目录应用概览代码结构与核心组件1. 初始化与布局 (__init__)2. 工具栏 (setup_t

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

Python实现AVIF图片与其他图片格式间的批量转换

《Python实现AVIF图片与其他图片格式间的批量转换》这篇文章主要为大家详细介绍了如何使用Pillow库实现AVIF与其他格式的相互转换,即将AVIF转换为常见的格式,比如JPG或PNG,需要的小... 目录环境配置1.将单个 AVIF 图片转换为 JPG 和 PNG2.批量转换目录下所有 AVIF 图