N3-1 - 数组 - convert-sorted-array-to-binary-search-tree
2024-08-31 09:41:39
题目描述:
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
升序数组,转二叉排序树
解题思路:
使用递归方法:
选取中间的节点作为root节点,其左侧的节点构成左子树(递归调用建树),右侧的节点构成右子树。
class Solution {
public:
TreeNode *sortedArrayToBST(vector<int> &num) {
if(num.empty())
return nullptr;//树为空
return sortedArrayToBSTCore( num,0,num.size()-1);//对num取引用,避免了复制
} TreeNode *sortedArrayToBSTCore(vector<int> &num, int begin,int end){
//递归建立二叉搜索树
if(end<begin)return nullptr;
//if(end==begin)return num[begin];//只有一个元素时不再递归调用子树。返回类型错误应该是 TreeNode *
//只有一个元素时,不会调用if,不再递归,返回一个节点。因此不用特殊判断该情况
int middle = (begin+end+1)/2; //取中间元素作为root节点,如果是偶数个元素,取中间偏后一个元素作为root节点
TreeNode *pRoot = new TreeNode (num[middle]);
if(middle>begin) //有左子树时
pRoot->left = sortedArrayToBSTCore(num,begin, middle-1); //middle已经被使用
if(middle<end)//有右子树
pRoot->right = sortedArrayToBSTCore(num,middle+1, end); return pRoot;
} };
注意:
1. 测试序列中,root的选择,当子树节点为奇数时,取中间即可(begin+end)/2,当子树节点为偶数时,取中间偏后的节点(begin+end+1)/2。由于整数除法,向下取整,可统一式子为(begin+end+1)/2。错误的写法(begin+end)/2+1;在奇数个节点时,在取了正中间节点的后一位。
2. 除2,可以使用右移>>。(更好一些)
最新文章
- (转)利用libcurl和国内著名的两个物联网云端通讯的例程, ubuntu和openwrt下调试成功(四)
- js自动提示查询添加功能(不是自动补全)
- 一个App Widget实例第一次创建时被调用
- Qt 多线程和网络编程学习
- mybaits3.2.8 别名包扫描通配符
- webstorm 添加文件模板
- 给自己保存份CSS初始值样式
- PQ分区魔术师v9.0 中文版
- 51 Nod 1119
- Java编程思想 - 第11章 持有对象
- 补码的来源以及为什么byte的最小值是-128
- webpack4+node合并资源请求, 实现combo功能(二十三)
- Effective Java 第三版——56. 为所有已公开的API元素编写文档注释
- CentOS 7 配置HTTPS加密访问SVN
- 面试官提出的问题应该怎么答?(如开发中使用过EasyUI吗?)
- js的回调函数详解
- 微软BI 之SSAS 系列 - 在 SQL Server 2012 下查看 SSAS 分析服务的模型以及几个模型的简单介绍
- execvp php-fpm reload使用的函数
- Linux strace命令详解
- C# 程序执行时间差