Leetcode No.108 Convert Sorted Array to Binary Search Tree(c++实现)
2021/7/6 17:42:26
本文主要是介绍Leetcode No.108 Convert Sorted Array to Binary Search Tree(c++实现),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1. 题目
1.1 英文题目
Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.
A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
1.2 中文题目
给定一个内部元素按照升序排列的数组,请将其转化成高度平衡的二叉搜索树。
1.3输入输出
输入 | 输出 |
---|---|
nums = [-10,-3,0,5,9] | [0,-3,9,-10,null,5] |
nums = [1,3] | [3,1] |
1.4 约束条件
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums is sorted in a strictly increasing order.
2. 实验平台
IDE:VS2019
IDE版本:16.10.1
语言:c++11
3. 程序
3.1 测试程序
#include "Solution.h" #include <vector> // std::vector #include<iostream> // std::cout using namespace std; // 主程序 int main() { // 输入 vector<int> nums= { -10, -3, 0, 5, 9 }; Solution solution; // 实例化Solution TreeNode* output = solution.sortedArrayToBST(nums); // 主功能 }
3.2 功能程序
3.2.1 最优算法
(1)代码
#pragma once #include<vector> // std::vector #include<algorithm> using namespace std; //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* sortedArrayToBST(vector<int>& nums) { if (nums.size() == 0) return nullptr; // 空数组情况 int mid = nums.size() / 2; // 定义中点值 TreeNode* node = new TreeNode(nums[mid]); auto leftTree = vector<int>(nums.begin(), nums.begin() + mid); // 左边树结构 auto rightTree = vector<int>(nums.begin() + mid + 1, nums.end()); // 右边树结构 if (mid != 0) // 左边树结构递归 node->left = sortedArrayToBST(leftTree); // 递归 if (mid != nums.size() - 1) node->right = sortedArrayToBST(rightTree); return node; } };
参考:https://blog.csdn.net/u012814856/article/details/77894863
(2)解读
参考:
https://blog.csdn.net/u012814856/article/details/77894863
4.其他知识
(1)树
- 二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别是二叉排序树。
- 平衡二叉树(Self-Balancing Binary search Tree)又被称为 AVL 数,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。
(2)c++结构体
a.作用
最主要的作用就是封装。封装的好处就是可以再次利用。让使用者不必关心这个是什么,只要根据定义使用就可以了。
b.C++中的结构体与类的区别
class中默认的成员访问权限是private的,而struct中则是public的。 (2)class继承默认是private继承,而从struct继承默认是public继承。
c. C++的结构体可以包含函数,而c的不可以
d. 利用构造函数定义
参考:https://blog.csdn.net/qq_33973359/article/details/105511966
e.struct和typedef struct
参考:https://www.cnblogs.com/qyaizs/articles/2039101.html
参考:https://www.cnblogs.com/zhengfa-af/p/8144786.html
这篇关于Leetcode No.108 Convert Sorted Array to Binary Search Tree(c++实现)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享