算法打卡day18|二叉树篇07|Leetcode 530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236. 二叉树的最近公共祖先

 算法题

Leetcode  530.二叉搜索树的最小绝对差

题目链接:530.二叉搜索树的最小绝对差

大佬视频讲解:二叉搜索树的最小绝对差视频讲解

个人思路

因为是在二叉搜索树求绝对差,而二叉搜索树是有序的,那就把它想成在一个有序数组上求最值,求差值。采用中序遍历的递归,遍历所有节点,求出最小值

解法
递归法

使用二叉搜索树的特性,利用中序遍历就能把二叉树按照递增 序列去遍历,如下图;

class Solution {TreeNode pre;// 记录上一个遍历的结点int result = Integer.MAX_VALUE;//存最小绝对值的结果public int getMinimumDifference(TreeNode root) {if(root==null)return 0;traversal(root);return result;}public void traversal(TreeNode root){if(root==null)return;//终止条件traversal(root.left); //左if(pre!=null){ //中result = Math.min(result,root.val-pre.val);//取差值绝对值最小}pre = root;traversal(root.right);//右}
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(n);(递归树的高度,如果是一个高度不平衡的树(例如链状结构)高度与n接近)

迭代法

中序遍历的迭代法模板,再加上前一个节点pre,遍历取最小绝对值;

class Solution {TreeNode pre;Stack<TreeNode> stack;public int getMinimumDifference(TreeNode root) {if (root == null) return 0;stack = new Stack<>();//模拟递归的栈TreeNode cur = root;//当前节点int result = Integer.MAX_VALUE;while (cur != null || !stack.isEmpty()) {if (cur != null) {stack.push(cur); // 将访问的节点放进栈cur = cur.left; // 左}else {cur = stack.pop(); if (pre != null) { // 中result = Math.min(result, cur.val - pre.val);}pre = cur;//上一个节点cur = cur.right; // 右}}return result;}
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(n);(递归栈的空间)


Leetcode 501.二叉搜索树中的众数

题目链接:501.二叉搜索树中的众数

大佬视频讲解:二叉搜索树中的众数视频讲解

个人思路

又是二叉搜索树,所以可以使用中序遍历使得遍历顺序为递增顺序,这样比较出现频率就可以和相邻的值比较(比较时可以使用pre指针和cur指针),最后就把出现频率最高的元素输出;

解法
递归法

这道题只需要遍历一次就可以找到所有的众数。

在遍历时,如果 频率count 等于 maxCount(最大频率),把这个元素加入到结果集中;频率count 大于 maxCount的时候,不仅要更新maxCount,而且要清空结果集,因为结果集之前的元素都失效了。

class Solution {ArrayList<Integer> resList;//结果集int maxCount;//最大出现频次int count;//当前节点频次TreeNode pre;//用来比较节点值是否相同public int[] findMode(TreeNode root) {resList = new ArrayList<>();maxCount = 0;count = 0;pre = null;//初始为空findMode1(root);int[] res = new int[resList.size()];for (int i = 0; i < resList.size(); i++) {res[i] = resList.get(i);}return res;}public void findMode1(TreeNode root) {if (root == null) {return;}findMode1(root.left);int rootValue = root.val;if (pre == null || rootValue != pre.val) { // 计数count = 1;} else {count++;}// 更新结果以及maxCountif (count > maxCount) {resList.clear();//清空失效的结果集resList.add(rootValue);//加入新的结果maxCount = count;} else if (count == maxCount) {resList.add(rootValue);}pre = root;findMode1(root.right);}
}

时间复杂度:O(n);(最差遍历一遍树)

空间复杂度:O(n);(递归树的高度h,结果集最多为n)

迭代法

使用栈模拟递归,

class Solution {public int[] findMode(TreeNode root) {TreeNode pre = null;Stack<TreeNode> stack = new Stack<>();List<Integer> result = new ArrayList<>();int maxCount = 0;int count = 0;TreeNode cur = root;while (cur != null || !stack.isEmpty()) {if (cur != null) {stack.push(cur);cur =cur.left;//左}else {cur = stack.pop();//中// 计数if (pre == null || cur.val != pre.val) {count = 1;}else {count++;}// 更新结果if (count > maxCount) {maxCount = count;result.clear();result.add(cur.val);}else if (count == maxCount) {result.add(cur.val);}pre = cur;cur = cur.right;//右}}//列表转数组,即result 列表中所有 Integer 元素转换为原始整数值的 int 类型数组。return result.stream().mapToInt(Integer::intValue).toArray();}
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(n);(使用栈,结果集大小)


Leetcode 236. 二叉树的最近公共祖先

题目链接:236. 二叉树的最近公共祖先

大佬视频讲解:二叉树的最近公共祖先视频讲解

个人思路

思路不清晰,主要是如何递归不太清楚。

解法
递归法

首先确定采用后序遍历,因为是需要找出公共祖先,所以先遍历左右节点,然后递归三步走

1.确定递归函数返回值以及参数

需要递归函数返回值,来说明是否找到节点q或者p,那么返回值为bool类型就可以了。

还要返回最近公共节点,可以利用上题目中返回值是TreeNode * ,那么如果遇到p或者q,就把q或者p返回,返回值不为空,就说明找到了q或者p。

2.确定终止条件

遇到空的话,因为树都是空了,所以返回空。

如果 root == q,或者 root == p,说明找到 q p ,则将其返回

3.确定单层递归逻辑

如果递归函数有返回值,搜索一条边和搜索整个树是有区别

搜索一条边的写法:

if (递归函数(root->left)) return ;if (递归函数(root->right)) return ;

搜索整个树写法:

left = 递归函数(root->left);  // 左
right = 递归函数(root->right); // 右
left与right的逻辑处理;         // 中 

在递归函数有返回值的情况下:如果要搜索一条边,递归函数返回值不为空的时候,立刻返回,如果搜索整个树,直接用一个变量left、right接住返回值,这个left、right后续还有逻辑处理的需要,也就是后序遍历中处理中间节点的逻辑(也是回溯

在这道题中,还要遍历根节点右子树(即使此时已经找到了目标节点了),因为要等left与right逻辑处理完之后才能返回。

其中处理left和right的逻辑如下:

如果left 和 right都不为空,说明此时root就是最近公共节点。

如果left为空,right不为空,就返回right,说明目标节点是通过right返回的,反之依然。如下图

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || root == p || root == q) { // 递归结束条件return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if(left == null && right == null) { // 若未找到节点 p 或 qreturn null;}else if(left == null && right != null) { // 若找到一个节点return right;}else if(left != null && right == null) { // 若找到一个节点return left;}else { // 若找到两个节点return root;}}
}

时间复杂度:O(n);(遍历二叉树)

空间复杂度:O(n);(递归树的高度,如果是一个高度不平衡的树(例如链状结构)高度与n接近)


以上是个人的思考反思与总结,若只想根据系列题刷,参考卡哥的网址代码随想录算法官网

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/281251.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

HTML + CSS 核心知识点- 定位

简述&#xff1a; 补充固定定位也会脱离文档流、不会占据原先位置 1、什么是文档流 文档流是指HTML文档中元素排列的规律和顺序。在网页中&#xff0c;元素按照其在HTML文档中出现的顺序依次排列&#xff0c;这种排列方式被称为文档流。文档流决定了元素在页面上的位置和互相之…

探索数据结构:双向链表的灵活优势

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ &#x1f388;&#x1f388;养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属专栏&#xff1a;数据结构与算法 贝蒂的主页&#xff1a;Betty’s blog 1. 前言 前面我们学习了单链表&#xff0c;它解决了顺序表中插入删除需…

深度学习——数据预处理

一、数据预处理 为了能用深度学习来解决现实世界的问题&#xff0c;我们经常从预处理原始数据开始&#xff0c; 而不是从那些准备好的张量格式数据开始。 在Python中常用的数据分析工具中&#xff0c;我们通常使用pandas软件包。 像庞大的Python生态系统中的许多其他扩展包一样…

知识蒸馏——深度学习的简化之道 !!

文章目录 前言 1、什么是知识蒸馏 2、知识蒸馏的原理 3、知识蒸馏的架构 4、应用 结论 前言 在深度学习的世界里&#xff0c;大型神经网络因其出色的性能和准确性而备受青睐。然而&#xff0c;这些网络通常包含数百万甚至数十亿个参数&#xff0c;使得它们在资源受限的环境下&…

中霖教育:注册会计师考试难度大吗?

注册会计师被很多人认为是非常具有挑战性的考试&#xff0c;内容涵盖《会计》《审计》《税法》《经济法》《财务成本管理》《公司战略与风险管理》&#xff0c;考的知识点多而复杂&#xff0c;需要牢牢掌握&#xff0c;所以很多人认为这项考试的难度非常大。 注册会计师考试分…

uniapp使用Echarts图表H5显示正常 打包app显示异常

uniapp使用Echarts在H5页面调试 调试完在H5正常显示 然后通过安卓机调试的时候 发现直接空白了 还有这个爆错 Initialize failed: invalid dom 我有多个图表、图表是通过v-for循环出来的 解决方案 原来是yarn直接安装Echarts 然后改成本地JS文件引入 gitbub文件地址 — dist/…

[python]bar_chart_race绘制动态条形图

最近在 B 站上看到了一个宝藏 up 主&#xff0c;名叫 "Jannchie见齐"&#xff0c;专门做动态条形图相关的数据可视化。 可以看到做出的效果还是很不错的&#xff0c;但工具使用的是 JS&#xff0c;不是 Python&#xff0c;于是尝试搜索了一下&#xff0c;看看 Python…

[C语言]——函数递归

目录 一.什么是递归 1.递归的思想&#xff1a; 二.递归的限制条件 三.递归举例 1.举例1&#xff1a;求n的阶乘 1.1分析和代码实现 1.2画图推演 2.举例2&#xff1a;顺序打印⼀个整数的每⼀位 2.1分析和代码实现 2.2画图推演 四.递归与迭代 1.举例3&#xff1a;求第…

Git全套教程一套精通git.跟学黑马笔记

Git全套教程一套精通git.跟学黑马笔记 文章目录 Git全套教程一套精通git.跟学黑马笔记1.版本管理工具概念2. 版本管理工具介绍2.1版本管理发展简史(维基百科)2.1.1 SVN(SubVersion)2.1.2 Git 3. Git 发展简史4. Git 的安装4.1 git 的下载4.2 安装4.3 基本配置4.4 为常用指令配置…

【机器学习】深入解析线性回归模型

&#x1f388;个人主页&#xff1a;豌豆射手^ &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;机器学习 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进…

STM32CubeMX+freeRTOS+事件组 多任务处理LED和串口打印

摘要:利用CubeMx配置freeeRTOS建立任务并使用事件组实现按键按下时 LED开关和打印信息到串口,上位机接收显示。 验证STM32CubeMx配置的FreeRTOS的任务和事件组使用 方案:按下Key1,绿灯亮或者灭,同时串口打印Key1被按下了到上位机;相关端口和串口配置省略。 新建三个任务…

VMware部署银河麒麟遇到的问题记录

1. 解决VMware Workstation安装VMware Tools显示灰色的办法 1.关闭虚拟机; 2.在虚拟机设置分别设置CD/DVD、CD/DVD2和软盘为自动检测三个步骤; 3.再重启虚拟机,灰色字即点亮。 2.Linux安装vmTool

Linux - 线程互斥和互斥锁

文章目录 前言一、为什么要线程互斥原子性 二、互斥锁互斥锁的创建与销毁互斥锁进行互斥 前言 前几节课&#xff0c;我们学习了多线程的基础概念&#xff0c;这节课&#xff0c;我们来对线程互斥和互斥锁的内容进行学习。 一、为什么要线程互斥 首先我们要明白&#xff0c;对…

Python模块-基础知识

Python模块-基础知识 1.模块分类&#xff1a; &#xff08;1&#xff09;自定义模块&#xff1a; 如果你自己写一个py文件&#xff0c;在文件内写入一堆函数&#xff0c;则它被称为自定义模块&#xff0c;即使用python编写的.py文件 &#xff08;2&#xff09;第三方模块&…

面向对象(C# )

面向对象&#xff08;C# &#xff09; 文章目录 面向对象&#xff08;C# &#xff09;ref 和 out传值调用和引用调用ref 和 out 的使用ref 和 out 的区别 结构体垃圾回收GC封装成员属性索引器静态成员静态类静态构造函数拓展方法运算符重载内部类和分布类 继承里氏替换继承中的…

BM23 二叉树的前序遍历

public class Solution {/*** 代码中的类名、方法名、参数名已经指定&#xff0c;请勿修改&#xff0c;直接返回方法规定的值即可** * param root TreeNode类 * return int整型一维数组*/public void preorder(List<Integer> list,TreeNode root){if(root null)return;l…

C语言刷题1

和黛玉学编程呀 这期就是普普通通题目和答案啦&#xff0c;大都也比较基础&#xff0c;适合初学者&#xff0c;下期我们就更单链表啦 求Snaaaaaaaaaaaaaaa的前5项之和&#xff0c;其中a是一个数字&#xff0c; 例如&#xff1a;222222222222222 int main() {int a 0;int n …

力扣---完全平方数

思路&#xff1a; 还是比较好想的&#xff0c;g[i]定义为和为 i 的完全平方数的最少数量。那么递推关系式是g[i]min(g[i-1],g[i-4],g[i-9],...)1&#xff0c;数组初始化是g[0]0,g[1]1。注意这里要对g[0]初始化&#xff0c;&#xff08;举个例子&#xff09;因为在遍历到g[4]时&…

如何快速搭建一个完整的vue2+element-ui的项目-二

技术细节-继续配置 提示&#xff1a;你以为这样就完了吗,其实还有很多东西需要我们自己手写的 例如&#xff1a; element-ui的配置样式重置配置src使用的配置elinst配置axios异步请求的二次封转配置语言国际化配置(这个看需求,我这里就不用配置了)vuex的配置mixins的配置开发环…

淘宝店铺如何从1688一键铺货?官方授权API接口,可满足多样化上货需求

那么新手卖家如何将1688的源头厂货一键铺货到淘宝店铺呢&#xff1f;下面我教大家几招&#xff1a; 1、通过淘宝复制一键复制上货 淘宝API接口采集 taobao.item_get 公共参数 名称类型必须描述keyString是调用key&#xff08;必须以GET方式拼接在URL中&#xff09;secretStr…