当前位置:网站首页>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;
}
边栏推荐
猜你喜欢
如何在您的Shopify商店中添加实时聊天功能?
Redis configuration and optimization of NoSQL
Huawei partners and Developers Conference 2022 | Kirin software cooperates with Huawei to jointly build the computing industry and create a digital intelligence future
The number of nodes of a complete binary tree [non-O (n) solution > Abstract dichotomy]
Taro---day1---搭建项目
What is the e-commerce conversion rate so abstract?
【说明】Jmeter乱码的解决方法
What problems should be evaluated before implementing MES management system
[description] solution to JMeter garbled code
什么是过孔式导电滑环?
随机推荐
完全二叉树的节点个数[非O(n)求法 -> 抽象二分]
Ten MySQL locks, one article will give you full analysis
Neural network of zero basis multi map detailed map
【说明】Jmeter乱码的解决方法
向excel中导入mysql中的数据表
I/O限制进程与CPU限制进程
[untitled]
Zhang Fan: the attribution of flying pig after advertising based on causal inference technology
Taro--- day1--- construction project
Set collection usage
Drug interaction prediction based on learning size adaptive molecular substructure
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
Solon 1.8.3 release, cloud native microservice development framework
Ai+ clinical trial patient recruitment | massive bio completed round a financing of $9million
Lodash realizes anti shake and throttling functions and native implementation
Deploy a mongodb single node server locally, enable auth authentication and enable oplog
DeepMind | 通过去噪来进行分子性质预测的预训练
Import the data table in MySQL into Excel
万字长文看懂商业智能(BI)|推荐收藏
【嵌入式基础】内存(Cache,RAM,ROM,Flash)