个人网站icp备案网,网站卡片设计,一个虚拟机怎么做两个网站,网站开发的方式本文是力扣LeeCode-LeeCode-501、二叉搜索树中的众数【二叉搜索树pre辅助节点DFS】 学习与理解过程#xff0c;本文仅做学习之用#xff0c;对本题感兴趣的小伙伴可以出门左拐LeeCode。
给你一个含重复值的二叉搜索树#xff08;BST#xff09;的根节点 root #xff0c;…本文是力扣LeeCode-LeeCode-501、二叉搜索树中的众数【二叉搜索树pre辅助节点DFS】 学习与理解过程本文仅做学习之用对本题感兴趣的小伙伴可以出门左拐LeeCode。
给你一个含重复值的二叉搜索树BST的根节点 root 找出并返回 BST 中的所有 众数即出现频率最高的元素。
如果树中有不止一个众数可以按 任意顺序 返回。
假定 BST 满足如下定义
结点左子树中所含节点的值 小于等于 当前节点的值结点右子树中所含节点的值 大于等于 当前节点的值左子树和右子树都是二叉搜索树
示例 1 输入root [1,null,2,2] 输出[2] 示例 2 输入root [0] 输出[0] 提示
树中节点的数目在范围 [1, 104] 内-10^5 Node.val 10^5
思路
思路一普通二叉树
首先这道题要求的是二叉搜索树如果为我们直接把它当成一颗普通⼆叉树也是可以直接解决的遍历存数组使用map统计频率最后取高频的一个或者多个数
思路二二叉搜索树
既然是搜索树它中序遍历就是有序的遍历有序数组的元素出现频率从头遍历那么⼀定是相邻两个元素作⽐较然后就把出现频率最⾼的元素输出即可出现相邻两个元素的情况可以使⽤pre指针和cur指针的技巧了但需要注意初始化的时候pre NULL实际上比较的是第⼀个元素
统计众数出现次数的代码 if (prenull){ // 第⼀个节点count1; // 频率为1} else if (pre.valcur.val) { // 与前⼀个节点数值相同count;} else{ // 与前⼀个节点数值不同,则复原count1;}pre cur; // 更新上⼀个节点本题要求的是返回众数集合/数组 1、正常逻辑第一遍先找出最⼤频率maxCount然后重新遍历⼀遍数组把出现频率为maxCount的元素放进众数集合里最终需要两遍
2、遍历一次数组(只需要遍历⼀遍⼆叉搜索树就求出了众数的集合)
maxCount需要最⼤频率的时候保存频率count ⼤于 maxCount的时候不仅要更新maxCount⽽且要清空结果集留着之前的结果集不对
实现代码
class Solution {TreeNode pre null;int count 0; // 统计频率int maxCount 0; // 最⼤频率ListInteger resList new ArrayList();public int[] findMode(TreeNode root) {searchBST(root); int[] result new int[resList.size()];for (int i0;iresList.size();i){result[i] resList.get(i);}return result;}void searchBST(TreeNode cur){if (curnull)return;searchBST(cur.left); // 左// 中if (prenull){ // 第⼀个节点count1;} else if (pre.valcur.val) { // 与前⼀个节点数值相同count;} else{ // 与前⼀个节点数值不同count1;}pre cur; // 更新上⼀个节点if (maxCountcount)resList.add(cur.val); // 如果和最⼤值相同放进resList中if (countmaxCount){ // 计数⼤于最⼤值频率maxCount count; // 更新最⼤频率resList.clear(); // 很关键的⼀步不要忘记清空resList之前resList⾥的元素都失效了resList.add(cur.val);}searchBST(cur.right); // 右return;}
}最重要的一句话做二叉树的题目首先需要确认的是遍历顺序 大佬们有更好的方法请不吝赐教谢谢
