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

701. 二叉搜索树中的插入操作-day18

由于二叉搜索树的中序遍历序列是单调递增的,因此二叉搜素树的中序遍历序列中的相同结点值一定相邻。只要得到二叉搜索树的中序遍历序列,即可得到每个结点值的出现次数,并得到众数。

使用递归实现中序遍历的做法是依次访问左子树、根结点和右子树,对于左子树和右子树使用同样的方法访问。

由于中序遍历序列中的相同结点值一定相邻,因此不需要存储完整的中序遍历序列,而是只需要存储上一个遍历到的结点值和出现次数。每次访问结点时,判断当前结点值和上一个结点值是否相等,更新当前结点值的出现次数,然后比较当前结点值的出现次数与最大出现次数,维护二叉搜索树中的众数。

如果当前结点值的出现次数等于最大出现次数,则将当前结点值添加到众数列表中。

如果当前结点值的出现次数大于最大出现次数,则将最大出现次数更新为当前结点值的出现次数,将众数列表清空后将当前结点值添加到众数列表中。

遍历结束之后,众数列表中的结点值即为二叉搜索树中的全部众数。

对于中序遍历序列中的任意两个相邻结点值,或者结点值不同,或者结点值相同且出现次数不同,因此同一个结点值最多在众数列表中出现一次,不会重复出现。
参考storm大神
`class Solution {
int prev;
int freq;
int maxFreq;
List modesList;

public int[] findMode(TreeNode root) {prev = Integer.MIN_VALUE;freq = 0;maxFreq = 0;modesList = new ArrayList<Integer>();inorder(root);int size = modesList.size();int[] modes = new int[size];for (int i = 0; i < size; i++) {modes[i] = modesList.get(i);}return modes;
}public void inorder(TreeNode node) {if (node == null) {return;}inorder(node.left);if (node.val == prev) {freq++;} else {prev = node.val;freq = 1;}if (freq == maxFreq) {modesList.add(node.val);} else if (freq > maxFreq) {maxFreq = freq;modesList.clear();modesList.add(node.val);}inorder(node.right);
}

}
`

http://www.jsqmd.com/news/482125/

相关文章:

  • java6
  • 1023: 巨人排队
  • 探秘2026荧光粉领域:口碑佳的企业都有谁,可靠的荧光粉哪家好精选实力品牌 - 品牌推荐师
  • L2-024 部落(简单的并查集)
  • 振动料斗怎么选?2026年口碑厂家大揭秘,振动料斗哪家好精选优质品牌解析 - 品牌推荐师
  • Windows系统木马病毒排查与防治方案
  • deepseek的人性化
  • 最近在研究一个基于三菱PLC和组态王的物流货物分拣控制系统,感觉挺有意思的,分享一下我的思路和代码实现
  • 分辨率与WLAN
  • 【卫星】GNSS多路径效应分析【含Matlab源码 15170期】
  • 【电池】LPV模型预测控制方法和耦合电热模型的电池状态估计【含Matlab源码 15171期】
  • VitaBench: Benchmarking LLM Agents with Versatile Interactive Tasks in Real-world Applications
  • 【电池】PMP算法的插电式混合动力车能量优化控制策略【含Matlab源码 15172期】
  • CSDN技术盲盒挑战全攻略
  • 【电磁】计算电阻率层析成像(ERT)表面和跨井(XBH)电极配置的2D和3D灵敏度分布【含Matlab源码 15173期】
  • 【电力系统】风电、光伏与储能(含电池和废弃矿井小型抽水蓄能)互补调度运行研究【含Matlab源码 15174期】
  • 软考高项-成本管理
  • 基于深度学习的工程车辆检测系统演示与介绍(YOLOv12/v11/v8/v5模型+Pyqt5界面+训练代码+数据集)
  • js之xml处理
  • 【卫星】基于matlab GNSS多路径效应分析【含Matlab源码 15170期】
  • 701. 二叉搜索树中的插入操作-day25
  • NATS 的基本安装及使用
  • 【电池】基于matlab LPV模型预测控制方法和耦合电热模型的电池状态估计【含Matlab源码 15171期】
  • 实时显示系统时间
  • 【电池】基于matlab PMP算法的插电式混合动力车能量优化控制策略【含Matlab源码 15172期】
  • 122. 买卖股票的最佳时机 II-day32
  • 【电磁】基于matlab计算电阻率层析成像(ERT)表面和跨井(XBH)电极配置的2D和3D灵敏度分布【含Matlab源码 15173期】
  • L2-023 图着色问题
  • 打工人上班摸魚小說-第十五章 地铁、跟踪与再也甩不掉的影子
  • 不用公网 IP!cpolar 让 OpenClaw 随时随地在线