当前位置: 首页 > news >正文

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

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

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

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

中间的逻辑有一点小绕,我第一次也做了20分钟左右才发现问题。具体代码如下:

class Solution {
public:int Min=INT_MAX;TreeNode*pre=nullptr;int result=0;void traversal(TreeNode* root){if(root==nullptr)return;traversal(root->left);if(pre==nullptr)pre=root;else{result=abs(root->val-pre->val);if(result<Min){Min=result;}pre=root;}traversal(root->right);}int getMinimumDifference(TreeNode* root) {traversal(root);return Min;}
};

总体思路:利用BST的特性:中序序列单调递增。使用两个指针来得出两个结点之间的差值。

注意:

  1. 要用绝对值,abs()

				if(result<Min){Min=result;}pre=root;

注意,就算result>Min,pre也是照常不误地移动的,所以这里的pre要放在if外面

501.二叉搜索树中的众数

一开始我想用哈希表来接收的2,因为键值对也能显示这个数的个数。但是全部录入哈希表之后,我发现哈希表没办法去遍历…最后没能做出了来。看了卡哥的视频之后,感觉双指针法确实妙。具体代码如下:

class Solution {
public:TreeNode*pre=nullptr;int count=0;int Maxcount=0;vector<int> result;void traversal(TreeNode* root){if(root==nullptr)return;traversal(root->left);if(pre==nullptr)count=1;else if(pre->val==root->val)count++;else if(pre->val!=root->val)count=1;pre=root;if(count==Maxcount)result.push_back(root->val);if(count>Maxcount){Maxcount=count;result.clear();result.push_back(root->val);}traversal(root->right);return;}vector<int> findMode(TreeNode* root) {traversal(root);return result;}
};

要点:

  • 二叉搜索树一定要用中序遍历!

  • 双指针法的核心逻辑:

    • 当pre指针与root指针值相等时,count++;反之,则count=1。

    • 当count==Maxcount的时候,直接放入result数组;而当count>Maxcount的时候,直接清空result数组,重新放入元素。好处:这样就可以少遍历一次。

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

这道题的思路是比较新奇的,具体代码如下:

class Solution {
public:TreeNode* traversal(TreeNode* root, TreeNode* p, TreeNode* q){if(root==NULL)return NULL;if(root==p||root==q)return root;TreeNode*left=traversal(root->left,p,q);TreeNode*right=traversal(root->right,p,q);if(left!=NULL&&right==NULL)return left;else if(left==NULL&&right!=NULL)return right;else if(left!=NULL&&right!=NULL)return root;elsereturn NULL;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return traversal(root,p,q);}
};

总体思路:

  • 返回值和参数都和主函数一样,这里返回值是结点类型(因为题目要求返回公共节点),在函数体内需要设置变量来接收。

  • 终止条件:

    • 当为null时返回null
    • 当这个结点就是p或者q的时候,我们要返回这个结点。这就是佯装成终止条件的终止行为,它对整个思路往往非常关键!
  • 单层递归逻辑:

    • 后序遍历:我们单层的思路是,利用该节点的孩子的信息,来做一些操作。所以我们肯定毫不犹豫的选择后序遍历。因为后序遍历就是在得知孩子的信息的基础上,对当前节点做一些操作。
    • 核心逻辑:回溯。即当该节点是p或q时,返回,然后作为上一层结点的左孩子结点信息。如果右孩子也不为null(传回了p或q),那么说明这个结点就是公共祖先,然后把自己往上传就行了。如果自己只有一个孩子不为null,说明自己不是祖先,这时就需要把这个孩子的信息上传,去寻找它的祖先。

http://www.mrgr.cn/news/16698.html

相关文章:

  • SPI通信(软件模拟)
  • -bash: ./log.sh: /bin/bash^M: 坏的解释器: 没有那个文件或目录
  • uni-app 微信小程序开发安装配置 HbuilderX 微信小程序开发工具
  • AI革命:清华大学揭秘大模型工具学习的未来
  • 桶排序【算法 14】
  • AcWing 897. 最长公共子序列
  • SpringBoot统一功能处理
  • 【C语言】十六进制、二进制、字节、位
  • 【测试】——开发模型与测试模型
  • JS打造一款你自己的专用字体:使用p5.js与JavaScript实现
  • Colorfy v3.26 — 修改版,超过2000种图片涂色
  • OpenCompass 评测 InternLM-1.8B 实践
  • B站评论区的力量:构建大语言模型微调数据集的新策略
  • 【经典面试题】Kafka为什么这么快?
  • 2024.8.31 Python,合并区间,用sort通过列表第一个元素给列表排序,三数之和,跳跃游戏
  • 网络压缩之网络剪枝(network pruning)
  • TDesign 微信小程序组件库配置
  • C#泛型相关
  • 通用后台管理系统实战演示(Vue3 + element-plus)汇总篇一
  • UML类图中的组合关系