求邯郸网站制作,网站可以随便创建么,桂林欣梦网络,软件开发工程师招聘简章pdf题目 给定一个有相同值的二叉搜索树#xff08;BST#xff09;#xff0c;找出 BST 中的所有众数#xff08;出现频率最高的元素#xff09;。
假定 BST 有如下定义#xff1a; 结点左子树中所含结点的值小于等于当前结点的值结点右子树中所含结点的值大于等于当前结点的…题目 给定一个有相同值的二叉搜索树BST找出 BST 中的所有众数出现频率最高的元素。
假定 BST 有如下定义 结点左子树中所含结点的值小于等于当前结点的值结点右子树中所含结点的值大于等于当前结点的值左子树和右子树都是二叉搜索树 例如
给定 BST [1,null,2,2], 返回[2].
提示如果众数超过1个不需考虑输出顺序
进阶你可以不使用额外的空间吗假设由递归产生的隐式调用栈的开销不被计算在内
思路
这道题目如果不是二叉搜索树的话应该怎么解题是二叉搜索树又应该如何解题两种方式做一个比较可以加深大家对二叉树的理解。
递归法
如果不是二叉搜索树
如果不是二叉搜索树最直观的方法一定是把这个树都遍历了用map统计频率把频率排个序最后取前面高频的元素的集合。
具体步骤如下
1、这个树都遍历了用map统计频率
至于用前中后序哪种遍历也不重要因为就是要全遍历一遍怎么个遍历法都行层序遍历都没毛病
这里采用前序遍历代码如下
// mapint, int key:元素value:出现频率
void searchBST(TreeNode* cur, unordered_mapint, int map) { // 前序遍历if (cur NULL) return ;map[cur-val]; // 统计元素频率searchBST(cur-left, map);searchBST(cur-right, map);return ;
}2、把统计的出来的出现频率即map中的value排个序
有的同学可能可以想直接对map中的value排序还真做不到C中如果使用std::map或者std::multimap可以对key排序但不能对value排序。
所以要把map转化数组即vector再进行排序当然vector里面放的也是pairint, int类型的数据第一个int为元素第二个int为出现频率。
bool static cmp (const pairint, int a, const pairint, int b) {return a.second b.second; // 按照频率从大到小排序
}vectorpairint, int vec(map.begin(), map.end());
sort(vec.begin(), vec.end(), cmp); // 给频率排个序3、取前面高频的元素
此时数组vector中已经是存放着按照频率排好序的pair那么把前面高频的元素取出来就可以了。
result.push_back(vec[0].first);
for (int i 1; i vec.size(); i) {// 取最高的放到result数组中if (vec[i].second vec[0].second) result.push_back(vec[i].first);else break;
}
return result;整体C代码如下
class Solution {
private:void searchBST(TreeNode* cur, unordered_mapint, int map) { // 前序遍历if (cur NULL) return ;map[cur-val]; // 统计元素频率searchBST(cur-left, map);searchBST(cur-right, map);return ;
}
bool static cmp (const pairint, int a, const pairint, int b) {return a.second b.second;
}
public:vectorint findMode(TreeNode* root) {unordered_mapint, int map; // key:元素value:出现频率vectorint result;if (root NULL) return result;searchBST(root, map);vectorpairint, int vec(map.begin(), map.end());sort(vec.begin(), vec.end(), cmp); // 给频率排个序result.push_back(vec[0].first);for (int i 1; i vec.size(); i) {// 取最高的放到result数组中if (vec[i].second vec[0].second) result.push_back(vec[i].first);else break;}return result;}
};所以如果本题没有说是二叉搜索树的话那么就按照上面的思路写
二叉搜索树
既然是搜索树它中序遍历就是有序的。
如图 中序遍历代码如下
void searchBST(TreeNode* cur) {if (cur NULL) return ;searchBST(cur-left); // 左处理节点 // 中searchBST(cur-right); // 右return ;
}遍历有序数组的元素出现频率从头遍历那么一定是相邻两个元素作比较然后就把出现频率最高的元素输出就可以了。
关键是在有序数组上的话好搞在树上怎么搞呢
这就考察对树的操作了。
在上一篇博客中我们就使用了pre指针和cur指针的技巧这次又用上了。
弄一个指针指向前一个节点这样每次cur当前节点才能和pre前一个节点作比较。
而且初始化的时候pre NULL这样当pre为NULL时候我们就知道这是比较的第一个元素。
代码如下
if (pre NULL) { // 第一个节点count 1; // 频率为1
} else if (pre-val cur-val) { // 与前一个节点数值相同count;
} else { // 与前一个节点数值不同count 1;
}
pre cur; // 更新上一个节点此时又有问题了因为要求最大频率的元素集合注意是集合不是一个元素可以有多个众数如果是数组上大家一般怎么办
应该是先遍历一遍数组找出最大频率maxCount然后再重新遍历一遍数组把出现频率为maxCount的元素放进集合。因为众数有多个
这种方式遍历了两遍数组。
那么我们遍历两遍二叉搜索树把众数集合算出来也是可以的。
但这里其实只需要遍历一次就可以找到所有的众数。
那么如何只遍历一遍呢
如果 频率count 等于 maxCount最大频率当然要把这个元素加入到结果集中以下代码为result数组代码如下
if (count maxCount) { // 如果和最大值相同放进result中result.push_back(cur-val);
}是不是感觉这里有问题result怎么能轻易就把元素放进去了呢万一这个maxCount此时还不是真正最大频率呢。
所以下面要做如下操作
频率count 大于 maxCount的时候不仅要更新maxCount而且要清空结果集以下代码为result数组因为结果集之前的元素都失效了。
if (count maxCount) { // 如果计数大于最大值maxCount count; // 更新最大频率result.clear(); // 很关键的一步不要忘记清空result之前result里的元素都失效了result.push_back(cur-val);
}关键代码都讲完了完整代码如下只需要遍历一遍二叉搜索树就求出了众数的集合
class Solution {
private:int maxCount 0; // 最大频率int count 0; // 统计频率TreeNode* pre NULL;vectorint result;void searchBST(TreeNode* cur) {if (cur NULL) return ;searchBST(cur-left); // 左// 中if (pre NULL) { // 第一个节点count 1;} else if (pre-val cur-val) { // 与前一个节点数值相同count;} else { // 与前一个节点数值不同count 1;}pre cur; // 更新上一个节点if (count maxCount) { // 如果和最大值相同放进result中result.push_back(cur-val);}if (count maxCount) { // 如果计数大于最大值频率maxCount count; // 更新最大频率result.clear(); // 很关键的一步不要忘记清空result之前result里的元素都失效了result.push_back(cur-val);}searchBST(cur-right); // 右return ;}public:vectorint findMode(TreeNode* root) {count 0;maxCount 0;pre NULL; // 记录前一个节点result.clear();searchBST(root);return result;}
};迭代法
只要把中序遍历转成迭代中间节点的处理逻辑完全一样。
下面我给出其中的一种中序遍历的迭代法其中间处理逻辑一点都没有变我从递归法直接粘过来的代码连注释都没改
代码如下
class Solution {
public:vectorint findMode(TreeNode* root) {stackTreeNode* st;TreeNode* cur root;TreeNode* pre NULL;int maxCount 0; // 最大频率int count 0; // 统计频率vectorint result;while (cur ! NULL || !st.empty()) {if (cur ! NULL) { // 指针来访问节点访问到最底层st.push(cur); // 将访问的节点放进栈cur cur-left; // 左} else {cur st.top();st.pop(); // 中if (pre NULL) { // 第一个节点count 1;} else if (pre-val cur-val) { // 与前一个节点数值相同count;} else { // 与前一个节点数值不同count 1;}if (count maxCount) { // 如果和最大值相同放进result中result.push_back(cur-val);}if (count maxCount) { // 如果计数大于最大值频率maxCount count; // 更新最大频率result.clear(); // 很关键的一步不要忘记清空result之前result里的元素都失效了result.push_back(cur-val);}pre cur;cur cur-right; // 右}}return result;}
};总结
本题在递归法中给出了如果是普通二叉树应该怎么求众数。
知道了普通二叉树的做法时候再进一步给出二叉搜索树又应该怎么求众数这样鲜明的对比相信会对二叉树又有更深层次的理解了。
在递归遍历二叉搜索树的过程中还介绍了一个统计最高出现频率元素集合的技巧 要不然就要遍历两次二叉搜索树才能把这个最高出现频率元素的集合求出来。
为什么没有这个技巧一定要遍历两次呢 因为要求的是集合会有多个众数如果规定只有一个众数那么就遍历一次稳稳的了。
最后给出对应的迭代法其实就是迭代法中序遍历的模板加上递归法中中间节点的处理逻辑。
