php怎么做网站后台,门户类网站开发多少钱,潍坊作风建设网站,wordpress主题极简题目如下#xff1a;
给你一个含重复值的二叉搜索树#xff08;BST#xff09;的根节点 root #xff0c;找出并返回 BST 中的所有 众数#xff08;即#xff0c;出现频率最高的元素#xff09;。
如果树中有不止一个众数#xff0c;可以按 任意顺序 返回。
假定 BS…题目如下
给你一个含重复值的二叉搜索树BST的根节点 root 找出并返回 BST 中的所有 众数即出现频率最高的元素。
如果树中有不止一个众数可以按 任意顺序 返回。
假定 BST 满足如下定义
结点左子树中所含节点的值 小于等于 当前节点的值结点右子树中所含节点的值 大于等于 当前节点的值左子树和右子树都是二叉搜索树 示例 1 输入root [1,null,2,2]
输出[2]示例 2
输入root [0]
输出[0]提示
树中节点的数目在范围 [1, 104] 内-105 Node.val 105
解题思路如下直接暴力的算法就是遍历一遍树然后用map记录最后再对map里的频率进行排序。但是这颗树是二叉搜索树所以我们要利用好特性在中序遍历的同时设置变了count和maxTime来记录下出现的次数其中当count大于maxTime时就可以动态改变最大值而当相等时就把该数弹进容器里
代码实现如下
class Solution {
public: int count0;int maxSize0;TreeNode*prenullptr;vectorintresult; void travel(TreeNode*cur){ if(curnullptr)return; travel(cur-left); if(prenullptr){count1;}//是空的话说明cur遍历到叶子了 else if(pre-valcur-val){count;} else {count1;} precur;//第一次 if(countmaxSize){ result.push_back(cur-val); } if(countmaxSize){ maxSizecount; result.clear(); result.push_back(cur-val); }travel(cur-right); } vectorint findMode(TreeNode* root) { travel(root); return result; }
};
