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

news/2024/9/23 9:28:38/

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

遇到在二叉搜索树上求什么最值,求差值之类的,都要思考一下二叉搜索树可是有序的,要利用好这一特点。

class Solution {
public:void trival(TreeNode* node, vector<int>& nums) {if (node == nullptr) return ;trival(node->left, nums);nums.push_back(node->val);trival(node->right, nums);}int getMinimumDifference(TreeNode* root) {// 遇到在二叉搜索树上求什么最值,求差值之类的,// 都要思考一下二叉搜索树可是有序的,要利用好这一特点。vector<int> nums;trival(root, nums);int result = INT_MAX;for (int i = 1; i < nums.size(); i++) {result = min(result, nums[i] - nums[i - 1]);}return result;}
};

需要领悟一下二叉树遍历上双指针操作,优先掌握递归
题目链接/文章讲解:https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html
视频讲解:https://www.bilibili.com/video/BV1DD4y11779

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

这种方法,对普通二叉树和搜索二叉树都行
对于递归函数,中序和前序都行,因为只是统计一下val的频率

class Solution {
public:void trival(TreeNode* node, unordered_map<int, int>& map,int& maxFreq) {if (node == nullptr) return ;trival(node->left, map, maxFreq);map[node->val]++;maxFreq = max(maxFreq, map[node->val]);trival(node->right, map, maxFreq);return;}vector<int> findMode(TreeNode* root) {unordered_map<int, int> map;vector<int> result;int maxFreq = 0;if (root == nullptr) return result;trival(root, map, maxFreq);// for (const auto& entry : map) {//     if (entry.second == maxFreq) {//         result.push_back(entry.first);//     }// }for (auto it = map.begin(); it != map.end(); ++it) {if (it->second == maxFreq) {result.push_back(it->first);}}return result;}
};

和 530差不多双指针思路,不过 这里涉及到一个很巧妙的代码技巧。
可以先自己做做看,然后看我的视频讲解。
https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html
视频讲解:https://www.bilibili.com/video/BV1fD4y117gp

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

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 确定返回条件// 如果是叶子节点if (root == nullptr || root == q || root == p) {return root;}// 在左子树中寻找p和q的最近公共祖先TreeNode* leftLCA = lowestCommonAncestor(root->left, p, q);// 在右子树中寻找p和q的最近公共祖先TreeNode* rightLCA = lowestCommonAncestor(root->right, p, q);// 中// 如果左右子树中都分别找到了p和q,则当前节点为最近公共祖先节点if (leftLCA && rightLCA) {return root;}// 如果只在左子树中找到了p和q,则左子树中的最近公共祖先即为最近公共祖先if (leftLCA) {return leftLCA;}// 如果只在右子树中找到了p和q,则右子树中的最近公共祖先即为最近公共祖先return rightLCA;}
};

本题其实是比较难的,可以先看我的视频讲解
https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html
视频讲解:https://www.bilibili.com/video/BV1jd4y1B7E2


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

相关文章

Unity入门理论+实践篇之Luna

创建世界的主角 父子物体 首先创建一个cube物体 可以观察到其在2D视角下的坐标为&#xff08;0&#xff0c;0&#xff09; 此时将cube物体拖拽到ldle_0下&#xff0c;如图所示&#xff0c;并将其坐标值改为&#xff08;2&#xff0c;2&#xff09; 此时再将ldle_0物体的坐标…

U盘无法打开?数据恢复与预防措施全解析

在日常生活和工作中&#xff0c;U盘已成为我们存储和传输数据的重要工具。然而&#xff0c;有时我们会遇到U盘无法打开的情况&#xff0c;这无疑给我们带来了诸多不便。本文将深入探讨U盘打不开的现象、原因及解决方案&#xff0c;并分享如何预防此类问题的发生。 一、U盘无法访…

Leetcode刷题笔记2:数组基础2

导语 leetcode刷题笔记记录&#xff0c;本篇博客记录数组基础1部分的题目&#xff0c;主要题目包括&#xff1a; 977.有序数组的平方 &#xff0c;209.长度最小的子数组 &#xff0c;59.螺旋矩阵II 知识点 滑动窗口 所谓滑动窗口&#xff0c;就是不断的调节子序列的起始位…

Day02:LeedCode977. 有序数组的平方 209.长度最小的子数组 59.螺旋矩阵II

详解:Day2:LeedCode977. 有序数组的平方 209.长度最小的子数组 59.螺旋矩阵II-CSDN博客 977. 有序数组的平方 给你一个按 非递减顺序 排序的整数数组 nums&#xff0c;返回 每个数字的平方 组成的新数组&#xff0c;要求也按 非递减顺序 排序。 示例 1&#xff1a; 输入&#…

Kubernetes和Docker对不同OS和CPU架构的适配关系

Docker Docker官网对操作系统和CPU架构的适配关系图 对于其他发行版本&#xff0c;Docker官方表示没有测试或验证在相应衍生发行版本上的安装&#xff0c;并建议针对例如Debian、Ubuntu等衍生发行版本上使用官方的对应版本。 Kubernetes X86-64 ARM64 Debian系 √ √ Re…

网页设计步骤总结

第一步&#xff1a;css重置 https://blog.csdn.net/BradenHan/article/details/132122504 第二步&#xff1a;媒体查询不同尺寸加载不同的css文件https://blog.csdn.net/Yi_Lesama/article/details/131184469 <!-- link元素中的CSS媒体查询 --> <link rel"styl…

探秘URL的奥义:JavaScript中轻松获取页面参数值的N种姿势【含代码示例】

探秘URL的奥义&#xff1a;JavaScript中轻松获取页面参数值的N种姿势【含代码示例】 URL基础知识补给站基础案例&#xff1a;直接解析URL案例一&#xff1a;使用URLSearchParams案例二&#xff1a;传统字符串分割法 高级策略&#xff1a;动态与安全案例三&#xff1a;封装与模块…

ITSS运维资质认证的含金量

什么是ITSS运维资质认证 ITSS运维资质认证是指经过机构评估和审核&#xff0c;对从事IT运维工作的人员进行能力认证和身份确认的过程。认证通过的个人或机构&#xff0c;被视为具备一定的技术水平和专业素养&#xff0c;能够在IT运维领域提供高质量的服务。ITSS运维资质认证是评…