(二叉树) 1382. 将二叉搜索树变平衡 ——【Leetcode每日一题】

news/2024/7/24 13:24:13/

❓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]

提示

  • 树节点的数目在 [ 1 , 1 0 4 ] [1, 10^4] [1,104] 范围内。
  • 1 < = N o d e . v a l < = 1 0 5 1 <= Node.val <= 10^5 1<=Node.val<=105

💡思路:中序遍历

  • 可以中序遍历把二叉树转变为有序数组,
  • 然后在根据有序数组构造平衡二叉搜索树。

🍁代码:(Java、C++)

Java

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {ArrayList<Integer> temp = new ArrayList<Integer>();//将有序树转成有序数组private void travesal(TreeNode root){if(root == null) return;travesal(root.left);temp.add(root.val);travesal(root.right);}//将有序数组转换成平衡二叉树private TreeNode toTree(int left, int right){if(left > right) return null;int mid = left + ((right - left) / 2);TreeNode root = new TreeNode(temp.get(mid));root.left = toTree(left, mid - 1);root.right = toTree(mid + 1, right);return root;}public TreeNode balanceBST(TreeNode root) {travesal(root);return toTree(0, temp.size() - 1);}
}

C++

/*** 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 {
private:vector<int> temp;//中序遍历将有序树转成有序数组void traversal(TreeNode* root){if(root == nullptr) return;traversal(root->left);temp.push_back(root->val);traversal(root->right);}//将有序数组转平衡二叉树TreeNode* toTree(int left, int right){if(left > right) return nullptr;int mid = left + ((right - left) / 2);TreeNode* root = new TreeNode(temp[mid]);root->left = toTree(left, mid - 1);root->right = toTree(mid + 1, right);return root;}
public:TreeNode* balanceBST(TreeNode* root) {traversal(root);return toTree(0, temp.size() - 1);}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),获得中序遍历的时间代价是 O ( n ) O(n) O(n);建立平衡二叉树的时建立每个点的时间代价为 O ( 1 ) O(1) O(1),总时间也是 O ( n ) O(n) O(n)。故时间复杂度为 O ( n ) O(n) O(n)
  • 空间复杂度 O ( n ) O(n) O(n),这里使用了一个数组作为辅助空间,存放中序遍历后的有序序列,故空间复杂度为 O ( n ) O(n) O(n)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/498815.html

相关文章

C++模板和模板的特化,模板的扩展和智能指针------(14)

模板 概念 模板的作用是实现类型通用&#xff0c;降低代码的冗余度 模板可以为一种算法定义不同类型的版本 实现机制&#xff1a; 复制代码使用类型参数突破类型的限制&#xff0c;丧失一定的类型安全 模板需要实例化才能使用&#xff0c;实例化由编译器完成 模板的分类 …

类似微信预览缩放保存插件previewImage.js

很好用的预览缩放保存插件。 插件源码如下&#xff1a; (function(){ let insideObject { // inputId : // 用于页面多图片预览时绑定相应预览图片 inputName:plantIconPath, // 用于表单提交 imageId:preview_img, // 用于预览图片的渲染 defaultImgPath : "&…

关于达芬奇调色台的那些事儿

对于从事影视后期调色制作的工作人员来说&#xff0c;调色台是再也熟悉不过的了。说白了&#xff0c;他们就是为了代替了鼠标和键盘。但是为什么我们还要花那些冤枉钱去专门购买达芬奇调色台呢&#xff1f; 原因很简单&#xff0c;调色台能够代替鼠标和键盘&#xff0c;但是鼠…

Tangent Element调色台的设计与功能

Tangent Element调色台的设计与功能 今天小编为大家介绍一款从设计到功能都十分优秀的调色台——Tangent Element调色台。相信他的存在能让调色工作变得更加高效和轻松。 相信从事影视工作的朋友都知道达芬奇调色台&#xff0c;达芬奇调色台现在是市场上的主流&#xff0c;也是…

JavaWeb之EL表达式和JSTL标签库

文章目录 EL表达式基本介绍EL表达式搜索域数据的顺序EL表达式输出Bean的普通属性&#xff0c;数组属性&#xff0c;List集合属性&#xff0c;Map集合属性EL表达式 - 运算关系运算逻辑运算算数运算empty运算三元运算. 点运算 和 [] 中括号运算符 EL表达式的11个隐含对象EL获取四…

建设一个网站需要多长时间?

&#x1f482; 个人网站:【海拥】【游戏大全】【神级源码资源网】&#x1f91f; 前端学习课程&#xff1a;&#x1f449;【28个案例趣学前端】【400个JS面试题】&#x1f485; 寻找学习交流、摸鱼划水的小伙伴&#xff0c;请点击【摸鱼学习交流群】 目录 前言网站建设的基本步骤…

petalinux 生成SDK报错排除

AAA: 在项目文件下新建Qt5文件夹文件夹内新建文件并且设置对应参数 文件夹路径&#xff1a; project-spec/meta-user/recipes-qt/qt5 新建文件 vim ./qt5/qt3d_%.bbappend vim ./qt5/qtquickcontrols2_%.bbappend vim ./qt5/qtserialbus_%.bbappend 文件内容 qt3d_%.bbap…

编程珠玑课后习题答案 第四章 编写正确的程序

1. 尽管我们的二分搜索证明历经曲折&#xff0c;但是按照某些标准来衡量还是不够完善。你会如何证明改程序没有运行时错误&#xff08;例如除数为 0、数值溢出、变量值超出声明的范围或者数组下标越界&#xff09;呢&#xff1f;如果有离散数学的基础知识&#xff0c;你能否使用…

是时候适配android14了

1、原来老项目中有用到前台Service的功能的app&#xff0c;需要在14当中制定服务类型&#xff0c;类型分类如下所示&#xff1a; 为了帮助开发者更有目的地定义面向用户的前台服务&#xff0c;Android 10 在 <service> 元素内引入了 android:foregroundServiceType 属性…

电脑嘟一声,然后卡顿的解决办法

网上关于此类的解释大都是硬盘坏了&#xff0c;但用硬盘监测工具&#xff0c;譬如CrystalDiskInfo.exe看到硬盘的状态都是没有问题。 后来找到真正的原因是电源选项设置问题&#xff0c;之前是1分钟关闭硬盘&#xff0c;改成永远不关闭即可。

解决电脑卡顿问题

1.解决电脑卡顿问题 a.检查 b.修复 c.重启 2.查看电脑是否正版 a.输入命令 b.显示信息

电脑系统卡顿,怎么解决

最近感觉系统卡卡的 别抓心挠肝的了 今天小编教你如何应对 No.1 设置任务管理器 1.按住CtrlShiftESC&#xff0c;打开任务管理器。查看占用CPU、内存、磁盘、比例较高的程序结束进程。&#xff08;有时软件异常导致CPU使用率较高就可以选择禁用它&#xff09; 2.选择启动…

电脑卡慢原因之磁盘占用100%

电脑刚重装完系统没多久就变得卡慢了&#xff0c;前几天一直凑合着用着&#xff0c;今天实在受不了了&#xff0c;点一下鼠标反应好长时间&#xff0c;还让不让人好好玩耍了。今天就花了一些时间彻底解决一下这个问题。 遇到这种情况&#xff0c;我首先查看了一下资源管理器&am…

电脑卡怎么办,简单步骤让电脑变快

随着时代的发展&#xff0c;电脑成了生活中必不可少的部分。但是&#xff0c;当你的电脑变慢了&#xff0c;怎么办呢&#xff1f;直接重新安装系统吗&#xff1f;那可能不是明智的选择&#xff01;电脑用的时间越长就越卡&#xff0c;这是很正常的现象&#xff0c;基本上是每个…

计算机搜索功能卡,电脑卡

本词条缺少概述图&#xff0c;补充相关内容使词条更完整&#xff0c;还能快速升级&#xff0c;赶紧来编辑吧&#xff01; 电脑使用过程中由内存&#xff0c;运行&#xff0c;硬件等原因造成的电脑反映缓慢现象。 中文名 电脑卡 类 型 硬件领 域 计算机 性 质 名词 电脑…

解决电脑卡顿的一系列操作

本篇从别处回答复制的&#xff0c;主要用作自己的备忘。&#xff08;不一定全部都要修改&#xff0c;我改完一项虚拟内存后就不怎么卡了&#xff09; 而且尝试完之后电脑的确不怎么卡了。 copy from :http://ask.zol.com.cn/x/1174226.html 一、清理磁盘和整理磁盘碎片。 1、在…

拷贝目录到另外一台服务器,并且保持原属性不变

rsync -avz /app/console/ root192.168.1.167:/app/ mv tool app acquirer cstc/ useradd -u 530 -g 530 -d /app/cstc cstc chown cstc:cstc /app/cstc cp -a /etc/skel/. /app/cstc chown -R cstc:cstc /app/cstc 你可以使用cp命令&#xff08;copy&#xff09;来复制文件。…

FWI 地震数据的认识

目录 1、数据来源。 1&#xff09;SEG 系列。 2&#xff09;OpenFWI 系列。 2、数据量&#xff0c;尺寸。 1&#xff09; SEG 包含两个数据集&#xff1a;SEGSaltData 和 SimulateData。 2&#xff09;OpenFWI 包含12个数据集&#xff1a; 3、地震数据对应的观测系统。…

CSPM项目管理专业人员能力评价证书报考条件与考试形势

2021年10月&#xff0c;中共中央、国务院发布的《国家标准化发展纲要》明确提出构建多层次从业人员培养培训体系&#xff0c;开展专业人才培养培训和国家质量基础设施综合教育。建立健全人才的职业能力评价和激励机制。由中国标准化协会&#xff08;CAS&#xff09;组织开展的项…

如何选显卡

1. NVIDIA Tesla(k40/k80) 专门用来做深度学习 2.Quadro &#xff08;专门用来做图像设计的显卡&#xff09; 3. GeForce (专业游戏显卡&#xff09; 那么问题来了&#xff0c;GeForce 能做深度学习吗&#xff1f; 答案是你自己用可以&#xff0c;但是不能在机房用&#xff0c…