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

027.将有序数组转换为二叉搜索树

题目链接:

108. 将有序数组转换为二叉搜索树

大概思路:

题目要求:

给一个升序数组,把它转化为高度平衡二叉搜索树。

高度平衡二叉树:

一个节点的左右子树高度差一定不超过1。

思路:

取数组中间作为分割点,然后划分左右区间,然后再取左右区间的中间节点作为分割点,然后继续划分下去,不断循环,直至二叉搜索树构造完成

数组构造二叉搜索树,用中间节点不断划分的话,那必然是平衡树,脑补下过程,最大差最多一颗树

递归三部曲:

1.确定递归函数参数和返回类型:

划分区间是闭区间[left, right],参数为数组,左右区间的数值

TreeNode* traversal(vector<int>& nums, int left, int right) {

2.明确终止条件:

当函数构造到函数最后一个节点,此时没有再按mid划分区间的话,+-1会让这个条件达成

if (left > right) return nullptr;

3.确定递归单层逻辑:

取数组中间的值,然后构造新节点返回,同时以这个数值中间值为分割点,划分左右区间,最后返回该节点

//可以避免两个节点值加起来突破内存上限的同时,
//也可以让数组长度为偶数的时候,取中间靠左的数组作为中间节点
int mid = left + ((right - left) / 2);

TreeNode* root = new TreeNode(nums[mid]);
root->left = traversal(nums, left, mid - 1);
root->right = traversal(nums, mid + 1, right);
return root;

4.总代码:      

class Solution {
private:
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = left + ((right - left) / 2);
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = traversal(nums, left, mid - 1);
        root->right = traversal(nums, mid + 1, right);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = traversal(nums, 0, nums.size() - 1);
        return root;
    }
};

 

相关文章:

  • 第五届传智杯-初赛【B组-题解】
  • 最全面的SpringMVC教程(一)——SpringMVC简介
  • OpenCV-Python小应用(六):车道线检测
  • 微信小程序介绍
  • matlab实现MCMC的马尔可夫转换MS- ARMA - GARCH模型估计
  • 华为云桌面Workspace,让你的办公更加舒适惬意
  • 基于优先级的时间片轮转调度算法(C语言实现)
  • 43特征01——特征值特征向量: 特征多项式、特殊矩阵 的特征值与特征向量、Hamilton-Cayley 定理
  • [毕业设计]机器学习的运动目标跟踪-opencv
  • Ubuntu 软件管理学习笔记
  • python中pytest库用法详解
  • CSRF漏洞简介
  • C/C++航空客运订票系统
  • 编译原理之词法分析器随笔和简单实现
  • 47 - 父子间的冲突
  • Java Agent 学习笔记
  • Java 网络编程(2):UDP 的使用
  • Java基本数据类型之Number
  • JS正则表达式精简教程(JavaScript RegExp 对象)
  • ReactNativeweexDeviceOne对比
  • Spring Boot快速入门(一):Hello Spring Boot
  • win10下安装mysql5.7
  • 从0搭建SpringBoot的HelloWorld -- Java版本
  • 复杂数据处理
  • 树莓派 - 使用须知
  • 线性表及其算法(java实现)
  • 摩拜创始人胡玮炜也彻底离开了,共享单车行业还有未来吗? ...
  • 说说我为什么看好Spring Cloud Alibaba
  • # 20155222 2016-2017-2 《Java程序设计》第5周学习总结
  • (ros//EnvironmentVariables)ros环境变量
  • (solr系列:一)使用tomcat部署solr服务
  • (三) diretfbrc详解
  • (十五)使用Nexus创建Maven私服
  • (原創) 未来三学期想要修的课 (日記)
  • (原創) 系統分析和系統設計有什麼差別? (OO)
  • (转载)CentOS查看系统信息|CentOS查看命令
  • (转载)微软数据挖掘算法:Microsoft 时序算法(5)
  • ****** 二十三 ******、软设笔记【数据库】-数据操作-常用关系操作、关系运算
  • .NET 设计一套高性能的弱事件机制
  • .NET 应用架构指导 V2 学习笔记(一) 软件架构的关键原则
  • []FET-430SIM508 研究日志 11.3.31
  • [20160902]rm -rf的惨案.txt
  • [AIR] NativeExtension在IOS下的开发实例 --- IOS项目的创建 (一)
  • [BZOJ4016][FJOI2014]最短路径树问题
  • [IE编程] IE中使网页元素进入编辑模式
  • [New Portal]Windows Azure Virtual Machine (3) 在VM上挂载磁盘
  • [NOIP 2015]Day.1 T2 信息传递 【最小环】
  • [Oh My C++ Diary]\t \n \r的用法
  • [python] 之 装饰器
  • [Python] 字典操作及方法总结
  • [Python]list.append字典的时候,修改字典会导致list内容变化的问题
  • [Thinking]三个行
  • [ZT] 浙江大学校长杨卫院士:研究生导师“十戒”
  • [技术选型] Node.js
  • [领域]javascript hacking guide part 6
  • 项目打包遇到的问题解决
  • Hihocoder 1324 希尔伯特曲线
  • 使用mysql命令来还原student表_MySql数据库备份与还原简单实例
  • 解决因为maven默认编译java下的.java文件而导致的错
  • JAVA编程思想读书笔记(一)--面向对象
  • mysql支持事务的储存引擎_mysql事务与mysql储存引擎
  • 阿里云视频点播技术认知
  • MySQL修改登陆密码
  • SpringCloud的概念理解,有这篇就够了
  • 调试https接口