leetcode 530.二叉搜索树的最小绝对差 、501.二叉搜索树中的众数 、236. 二叉树的最近公共祖先

news/2024/7/25 19:56:21/文章来源:https://blog.csdn.net/huiNB/article/details/139263508
leetcode 530.二叉搜索树的最小绝对差 、501.二叉搜索树中的众数 、236. 二叉树的最近公共祖先
leetcode 530.二叉搜索树的最小绝对差
题目链接:https://leetcode.cn/problems/maximum-binary-tree/description/
题目:

给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数,其数值等于两值之差的绝对值。

示例 1:

在这里插入图片描述

输入:root = [4,2,6,1,3]
输出:1

示例 2:
在这里插入图片描述
输入:root = [1,0,48,null,null,12,49]
输出:1

提示:
树中节点的数目范围是 [2, 104]
0 <= Node.val <= 105

解题思路

这道题还是之前说的用类双指针的方法解决,用一个pre记录前一个结点和一个变量存储差值。然后去中序遍历。具体实现代码:

代码:
class Solution {TreeNode pre = null; //前序指针int res = Integer.MAX_VALUE; //记录变量public int getMinimumDifference(TreeNode root) {travese(root);return res;}public void travese(TreeNode root) {if (root == null) return; //递归终止条件travese(root.left); //左if (pre != null) {res = Math.min(res,root.val - pre.val);  //中}pre = root; //前序指针跟着前进travese(root.right); //右}
}
leetcode 501 二叉搜索树中的众数
题目链接:https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/
题目

给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。

如果树中有不止一个众数,可以按 任意顺序 返回。

假定 BST 满足如下定义:

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

示例 1:
在这里插入图片描述

输入:root = [1,null,2,2]
输出:[2]

示例 2:
输入:root = [0]
输出:[0]

提示:
树中节点的数目在范围 [1, 104] 内
-105 <= Node.val <= 105

进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)

解题思路

这道题继续沿用上面的解法,不过要记录所有的总数,那需要一个数组去记录和两个辅助变量去记录节点值出现的次数和当前的最大数。在中序遍历过程中,当前节点值和前一个节点值不一致时,重新赋值为1同时,还要判断之前的节点值出现的次数是否是跟最大次数一样,是的话,就要添加到结果数组中,或者说,其出现的次数大于最大次数,那要重新记录,即清空数组,把该值重新添加到数组。具体实现代码:

代码:
class Solution {TreeNode pre = null; //前序指针int count = 0; //出现的次数int Maxcount = 0; //最大次数List<Integer> res = new ArrayList<>(); //结果数组public int[] findMode(TreeNode root) {searchBST(root);int[] result = new int[res.size()]; //因为题目要求返回int[]类型,而结果存储是List中,所以要取出来放在一个int[]中。for (int i = 0; i < result.length; i++) {result[i] = res.get(i);}return result;}public void searchBST(TreeNode root) {if (root == null) return; //递归终止条件searchBST(root.left); //左if (pre == null || pre.val != root.val) { //遍历开始或者不算同个值,count为1count = 1;}else { //是同个值,count++count++;}if (count == Maxcount) { //count==最大次数,将该值添加到结果数组中res.add(root.val);}if (count > Maxcount) { //count大于最大次数,更新结果数组和最大次数值Maxcount = count;res.clear();res.add(root.val);}pre = root; //前序指针继续前进searchBST(root.right); //右}
}

这道题也可以用迭代法做,思想是一样的,顺便回顾一下中序遍历的迭代法

class Solution {public int[] findMode(TreeNode root) {TreeNode pre = null;Stack<TreeNode> s = new Stack<TreeNode>();List<Integer> res = new ArrayList<>();int maxcount = 0;int count = 0;TreeNode cur = root;while (cur != null || !s.isEmpty()) {if (cur!=null) {s.push(cur);cur = cur.left;}else {cur = s.pop();if (pre == null || pre.val != cur.val) {count = 1;}else {count++;}if (count == maxcount) {res.add(cur.val);}if (count > maxcount) {maxcount = count;res.clear();res.add(cur.val);}pre = cur;cur = cur.right;}}return res.stream().mapToInt(Integer::intValue).toArray();}
}
leecode 236. 二叉树的最近公共祖先
题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
题目

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

示例 1:
在这里插入图片描述

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2:
在这里插入图片描述

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5
解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3:

输入:root = [1,2], p = 1, q = 2
输出:1

提示:

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

解题思路

要找两个结点的最近公共祖先,那就要用到后序遍历了,因为只有后序遍历才能拿到左右子树的返回值。那如何判断一个结点是结点p和结点q的公共祖先呢。直接去递归,遇到p或者q直接返回。即如果递归遍历遇到q,就将q返回,遇到p 就将p返回,那么如果 左右子树的返回值都不为空,说明此时的中节点,一定是q 和p 的最近祖先。那在拿到左右子树的返回值,怎么处理呢。可以这样处理,如果left 和 right都不为空,说明此时root就是最近公共节点。如果left为空,right不为空,就返回right,说明目标节点是通过right返回的,同样,如果right为空,left不为空,就返回left,说明目标节点是通过left返回的。具体实现代码为:

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

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

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

相关文章

BUUCTF-misc刷题

被嗅探的流量1 用wireshark打开附件&#xff0c;Ctrlf&#xff0c;然后搜索flag&#xff0c;我们在这么多数据包中搜索带有flag字符的 然后第一个包中上传了一个名叫flag的.jpg文件 然后直接ctrlf&#xff0c;搜索flag{ 得到flag&#xff1a;flag{da73d88936010da1eeeb36e945e…

php 连接sqlserver步骤

1.首先要确定使用的是sqlserver的哪个版本&#xff0c;比如sqlserver2012 2.确定服务器是64位还是32位的 3.确认一下使用php的哪个版本&#xff0c;比如php7.1 SQL Server 的 Microsoft PHP 驱动程序 Microsoft Drivers for PHP 支持矩阵 - PHP drivers for SQL Server | Mi…

香橙派Kunpeng Pro深度测评:开发者的新选择

文章目录 前言&#xff1a;一、开发板外观与介绍1.接口介绍2.按键以及LED的介绍 二、开发板上电以及系统启动三、更新安装相关命令四、查看相关配置五、vim个性化配置六、开发板网络测试1.网口测试&#xff1a;2.WiFi模块测试&#xff1a; 七、扩展引脚功能测试1.TFTP传输文件2…

C++---运算符重载

运算符重载介绍 在类中重新定义运算符&#xff0c;赋予运算符新的功能以适应类的运算&#xff0c;就称为运算符重载。 运算符重载是一种形式的C多态,它使得对象操作更直观,本质上也是属于函数重载。 实际上&#xff0c;我们已经在不知不觉之中使用了运算符重载。例如&#xff…

spark的简单学习一

一 RDD 1.1 RDD的概述 1.RDD&#xff08;Resilient Distributed Dataset&#xff0c;弹性分布式数据集&#xff09;是Apache Spark中的一个核心概念。它是Spark中用于表示不可变、可分区、里面的元素可并行计算的集合。RDD提供了一种高度受限的共享内存模型&#xff0c;即RD…

如何基于springboot构建cas最新版源码?

环境准备 下载JDK21 https://download.oracle.com/java/21/archive/jdk-21.0.2_windows-x64_bin.zip下载gradle 8.5并配置环境变量 https://gradle.org/next-steps/?version8.5&formatbin下载项目git clone http://gitlab.ruishan.cc/meta/anka-authentication.git 开始…

【CSP CCF记录】201909-1 小明种苹果

题目 过程 #include<bits/stdc.h> using namespace std; int N,M; long long tree[1010]; int main() {cin>>N>>M;long long result0,max0;//result剩余苹果&#xff0c;max最大疏果个数 int id0;//id最大疏果的果树编号 for(int i1;i<N;i){long long b0…

【LeetCode】【9】回文数(1047字)

文章目录 [toc]题目描述样例输入输出与解释样例1样例2样例3 提示进阶Python实现 个人主页&#xff1a;丷从心 系列专栏&#xff1a;LeetCode 刷题指南&#xff1a;LeetCode刷题指南 题目描述 给一个整数x&#xff0c;如果x是一个回文整数&#xff0c;返回true&#xff1b;否…

Java数组的使用

Java数组的使用 前言一、数组基本用法什么是数组注意事项创建数组基本语法代码示例注意事项 数组的使用代码示例获取长度 & 访问元素注意事项 下标越界遍历数组编程求平均成绩Mathrandom类现有100个学生&#xff0c;编程求平均成绩 使用 for-each 遍历数组 二、数组作为方法…

解线性方程组——最速下降法及图形化表示 | 北太天元 or matlab

一、思路转变 A为对称正定矩阵&#xff0c; A x b Ax b Axb 求解向量 x x x这个问题可以转化为一个求 f ( x ) f(x) f(x)极小值点的问题&#xff0c;为什么可以这样&#xff1a; f ( x ) 1 2 x T A x − x T b c f(x) \frac{1}{2}x^TAx - x^Tb c f(x)21​xTAx−xTbc 可…

tty/pty/console/getty/shell/telnet

tty 终端(termimal)= tty(Teletypewriter, 电传打印机),作用是提供一个命令的输入输出环境,在linux下使用组合键ctrl+alt+T打开的就是终端,可以认为terminal和tty是同义词。 tty泛指所有的终端设置,这些是真实存在的设备。 通过tty命令可以查看当前终端连接的设备。…

Linux 一键部署alfresco 6

alfresco 前言 Alfresco是一个流行的企业级开源内容管理系统和协作平台。它提供了丰富的功能,包括文档管理、记录管理、协作工具、工作流管理、搜索和版本控制等。Alfresco还具有灵活的部署选项,可以作为本地部署的软件或云服务来使用。 该平台可以帮助组织管理和存储各种类…

WPS文件没有保存怎么恢复?5个解决方案轻松恢复!

“我在WPS上编辑了一个文件&#xff0c;但是还没来得及将它保存&#xff0c;我不小心就退出软件了&#xff0c;现在不知道有什么方法可以恢复WPS文件呢&#xff1f;大家可以帮帮我吗” WPS作为一款功能强大且用户友好的软件&#xff0c;给我们的工作带来了很多的便利。但我们在…

适用于Android的最佳数据恢复软件

如果您的 Android 设备崩溃&#xff0c;您需要找到一种方法来取回您的数据。幸运的是&#xff0c;有许多数据恢复程序可以帮助您恢复丢失的文件。有些是免费的&#xff0c;而另一些则需要付费。这是适用于Android设备的最佳数据恢复软件列表。 什么是数据恢复软件&#xff1f; …

紫光展锐前沿探索 | 满足未来6G多差异化应用场景的技术体系思考

在6G架构/系统设计中&#xff0c;紫光展锐提出了未来6G空口“一体多翼”的技术体系概念&#xff0c;即“Big-Lite Multi-RAT”。本文将详细对该技术体系展开介绍。 “一体多翼”技术体系通过 “体”&#xff08;Big RAT&#xff09;和“翼”&#xff08;Lite RAT&#xff09;的…

Java语言ADR药物不良反应系统源码Java+IntelliJ+IDEA+MySQL一款先进的药物警戒系统

Java语言ADR药物不良反应系统源码JavaIntelliJIDEAMySQL一款先进的药物警戒系统源码 ADR药物不良反应监测系统是一个综合性的监测平台&#xff0c;旨在收集、报告、分析和评价药品在使用过程中可能出现的不良反应&#xff0c;以确保药品的安全性和有效性。 以下是对该系统的详细…

C#【进阶】俄罗斯方块

俄罗斯方块 文章目录 Test1_场景切换相关BeginScene.csBegionOrEndScene.csEndScene.csGame.csGameScene.csISceneUpdate.cs Test2_绘制对象基类和枚举信息DrawObject.csIDraw.csPosition.cs Test3_地图相关Map.cs Test4_坐标信息类BlockInfo.cs Test5_板砖工人类BlockWorker.…

04_前端三大件JS

文章目录 JavaScript1.JS的组成部分2.JS引入2.1 直接在head中通过一对script标签定义脚本代码2.2创建JS函数池文件&#xff0c;所有html文件共享调用 3.JS的数据类型和运算符4.分支结构5.循环结构6.JS函数的声明7.JS中自定义对象8.JS_JSON在客户端使用8.1JSON串格式8.2JSON在前…

Python与OpenCV:图像处理与计算机视觉实战指南

前言 OpenCV&#xff08;Open Source Computer Vision Library&#xff09;是一个开源的计算机视觉和机器学习软件库&#xff0c;它包含了数百种计算机视觉算法&#xff0c;包括图像处理、视频分析、物体检测、面部识别等。结合Python语言的强大功能&#xff0c;OpenCV可以用于…

java医院管理系统源码(springboot+vue+mysql)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的医院管理系统。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 医院管理系统的主要使用者分…