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

二叉树(二)

98.验证二叉树

中序遍历二叉树,每次遍历存下当前节点的值,遍历到下一个节点比较,根据二叉搜索树的特性,左<中<右有:

如果当前值小于或等于上一个的值,说明不是二叉搜索树

如果当前值大于上一个节点的值,继续遍历直到遍历完整棵树

    TreeNode* pre = NULL;bool isValidBST(TreeNode* root) {if (root == NULL) return true;bool lf = isValidBST(root->left);if (pre && pre->val >= root->val) return false; pre = root;bool rg = isValidBST(root->right);return lf&&rg;}

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

根据二叉搜索树的特性,最小绝对查一定出现在一颗子树的根和他的左右儿子的差值上,依旧使用中序遍历

    int res = INT_MAX;TreeNode* pre = NULL;int getMinimumDifference(TreeNode* root) {if (root == NULL) return res;int lf = getMinimumDifference(root->left);if (pre) {int a = root->val - pre->val;res = min(res, a);}pre = root;int rg = getMinimumDifference(root->right);return res;}

501.二叉搜索树中的众数

一个比较直接的方法就是用map存每一个值出现的频率,然后导出最大频率对应的数值

既然是二叉搜索树,还是采用中序遍历来实现对结果处理

 vector<int> res;TreeNode* pre = NULL;int count1 = 0; // 用来计算频率int count2 = 0;// 用来存最大频率void dfs(TreeNode* root){if (root == NULL) return;dfs(root->left);if (pre == NULL) count1 = 1;else if (pre->val == root->val) count1++;else count1 = 1;pre = root;if (count1 == count2) res.push_back(root->val); // 出现最大频率就将root放进结果集,这可以用来处理多个众数的情况if (count1 > count2) { // 出现频率更高的数,清空结果集,并将该数加入数组count2 = count1;res.clear();res.push_back(root->val);}dfs(root->right);return;}vector<int> findMode(TreeNode* root) {count1 = 0;count2 = 0;res.clear();dfs(root);return res;}

http://www.xdnf.cn/news/10758.html

相关文章:

  • 深入理解前端DOM:现代Web开发的基石
  • Ansys Zemax | 手机镜头设计 - 第 4 部分:用 LS-DYNA 进行冲击性能分析
  • Android Native 内存泄漏检测全解析:从原理到工具的深度实践
  • 提取 PDF 文件中的文字以及图片中的文字
  • 从 iPhone 备份照片: 保存iPhone图片的5种方法
  • 计算机基础知识(第三篇)
  • 如何监测光伏系统中的电能质量问题?分布式光伏电能质量解决方案
  • [Java 基础]运算符,将盒子套起来
  • 如何提高工作效率
  • 企业即时通讯平台,助力企业数字化转型的即时通讯工具
  • 【AI Study】第三天,Python基础 - NumPy(1)
  • 【设计模式-4.7】行为型——备忘录模式
  • 欢乐熊大话蓝牙知识14:用 STM32 或 EFR32 实现 BLE 通信模块:从0到蓝牙,你也能搞!
  • 机器人现可完全破解验证码:未来安全技术何去何从?
  • 【JAVA版】意象CRM客户关系管理系统+uniapp全开源
  • GoFrame框架深度解析:从gset模块看高效Go开发的实战之道
  • Java复习Day26
  • 2025年微信小程序开发:AR/VR与电商的最新案例
  • windows修改跃点数调整网络优先级
  • Leetcode - 周赛 452
  • 帝可得- 人员管理
  • vue+cesium示例:地形开挖(附源码下载)
  • 进程——环境变量及程序地址空间
  • vscode配置lua
  • React从基础入门到高级实战:React 高级主题 - React 微前端实践:构建可扩展的大型应用
  • Ubuntu 系统部署 MySQL 入门篇
  • 本地部署开源防病毒引擎 ClamAV 并实现外部访问(Windows 版本)
  • 研发型企业如何面对源代码保密问题
  • 不动产登记区块链系统(Vue3 + Go + Gin + Hyperledger Fabric)
  • 焊缝缺陷焊接缺陷识别分割数据集labelme格式5543张4类别