当前位置:网站首页>1382. 将二叉搜索树变平衡-常规方法
1382. 将二叉搜索树变平衡-常规方法
2022-06-27 23:12:00 【Mr Gao】
1382. 将二叉搜索树变平衡
给你一棵二叉搜索树,请你返回一棵 平衡后 的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法,请你返回任意一种。
如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 1 ,我们就称这棵二叉搜索树是 平衡的 。
示例 1:
输入:root = [1,null,2,null,3,null,4,null,null]
输出:[2,1,3,null,null,null,4]
解释:这不是唯一的正确答案,[3,1,4,null,2,null,null] 也是一个可行的构造方案。
示例 2:
输入: root = [2,1,3]
输出: [2,1,3]
解题代码如下:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
int len;
void or_search(struct TreeNode* root){
if(root){
or_search(root->left);
len++;
or_search(root->right);
}
}
void or_search2(struct TreeNode* root,int *a){
if(root){
or_search2(root->left,a);
a[len++]=root->val;
or_search2(root->right,a);
}
}
void creat_root(struct TreeNode** root,int *a,int low,int high){
if(low<=high){
int mid=(low+high)/2;
(*root)->val=a[mid];
(*root)->left=(struct TreeNode*)malloc(sizeof(struct TreeNode));
(*root)->right=(struct TreeNode*)malloc(sizeof(struct TreeNode));
creat_root(&((*root)->left),a,low,mid-1);
creat_root(&((*root)->right),a,mid+1,high);
}
else{
(*root)=NULL;
}
}
struct TreeNode* balanceBST(struct TreeNode* root){
len=0;
or_search(root);
struct TreeNode* re=(struct TreeNode*)malloc(sizeof(struct TreeNode));
int *a=(int *)malloc(sizeof(int)*len);
len=0;
or_search2(root,a);
printf("len %d ",len);
creat_root(&re,a,0,len-1);
return re;
}
边栏推荐
- 药物发现综述-02-分子性质预测
- Can you open an account for stock trading in flush? Is it safe?
- 手机股票开户安全吗,买股票在哪开户?
- Comprehensive evaluation of free, easy-to-use and powerful open source note taking software
- Solon 1.8.3 release, cloud native microservice development framework
- Class文件结构和字节码指令集
- Intensive reading of transformer thesis paragraph by paragraph
- The research group of Xuyong and duanwenhui of Tsinghua University has developed an efficient and accurate first principles electronic structure deep learning method and program
- Qu'est - ce que la numérisation? Qu'est - ce que la transformation numérique? Pourquoi les entreprises choisissent - elles la transformation numérique?
- [open source] open source system sorting - Examination Questionnaire, etc
猜你喜欢
MySQL 18: execution of write statements
美团动态线程池实践思路已开源
药物发现综述-01-药物发现概述
如何理解 Transformer 中的 Query、Key 与 Value
How to build dual channel memory for Lenovo Savior r720
Taro--- day1--- construction project
Web3 技术初体验以及相关学习资料
Adobe Premiere基础-声音调整(音量矫正,降噪,电话音,音高换挡器,参数均衡器)(十八)
Message Oriented Middleware for girlfriends
LMSOC:一种对社会敏感的预训练方法
随机推荐
Modular development
How to read a paper
Adobe Premiere基础-常用的视频特效(裁剪,黑白,剪辑速度,镜像,镜头光晕)(十五)
哪个证券炒股开户佣金是最便宜,最安全的
electron窗口背景透明无边框(可用于启动页面)
Review of drug discovery-02-prediction of molecular properties
Overview of drug discovery-01 overview of drug discovery
What is the application scope and function of the conductive slip ring of single crystal furnace
[description] solution to JMeter garbled code
.mp4视频测试地址
Solve storage problems? WMS warehouse management system solution
The research group of Xuyong and duanwenhui of Tsinghua University has developed an efficient and accurate first principles electronic structure deep learning method and program
[DNS resolution] set the name DNSPod resolution for domain name access of COM
Is it safe to open an account for mobile stocks? Where can I open an account for buying stocks?
Implementation of timed tasks in laravel framework
【牛客讨论区】第四章:Redis
电商转化率这么抽象,到底是个啥?
Lefse analyzes the local implementation method with all installation files and details to ensure success.
Cloud assisted privacy collection intersection (server assisted psi) protocol introduction: Learning
想开户买股票,在网上办理股票开户安全吗?