脚本宝典收集整理的这篇文章主要介绍了206. 反转链表(C++),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数。
(出现频率最高的元素)
假定 BST 有如下定义:
例如:给定 BST [1,null,2,2]
,
1
2
/
2
返回[2].
提示:如果众数超过1个,不需考虑输出顺序#
无视二叉搜索树的性质,直接对二叉树进行遍历。
同时使用哈希表对不同数值的频次进行统计。
将哈希表排序后再遍历map找出频次最高的一组或多组数值。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
// 编写两个私有的函数用于遍历BST
private:
void searchBST(TreeNode* cur, unordered_map<int, int> &map) {
// 设置终止条件
if (cur == nullptr) return;
map[cur->val]++;
searchBST(cur->left, map);
searchBST(cur->right, map);
}
// 自定义sort比较函数
// static修饰表示该文件只能在本文件中调用
bool static cmp(pair<int, int> a, pair<int, int> b) {
return a.second > b.second;
}
public:
vector<int> findMode(TreeNode* root) {
vector<int> res;
unordered_map<int, int> map;
// 先考虑特殊情况
if (root == nullptr) return res;
searchBST(root, map);
vector<pair<int, int>> vec(map.begin(), map.end());
// 先使用自定义比较规则进行排序
sort(vec.begin(), vec.end(), cmp);
res.push_back(vec[0].first);
// 还要考虑频率相同的并列元素
for (int i = 1; i < vec.size(); i++) {
if (vec[i].second == vec[0].second)
res.push_back(vec[i].first);
else break;
}
return res;
}
};
二叉搜索树(Binary Search Tree)的主要性质在于:
所以如果对二叉树进行中序遍历的话,所得的数列表必定是单调递增的,相等的数值必定邻近。
// 先设置递归终止条件
if (cur == nullptr) return;
// 中序遍历
searchBST(cur->left);
// 处理当前节点
if (pre == nullptr) {
// 说明当前是根节点
count = 1;
} else if (pre->val == cur->val) {
// 临近节点值相同,原子递增
count++;
} else {
// 临界节点值不同,重新进行计数
count = 1;
}
pre = cur;
因此我们在遍历二叉树时,设置一个pre
来定位当前结点的前一个结点。因为临近值的结点必定是相邻的,无非有以下三种情况:
根节点:遍历首位结点时,pre
为空,此时初始化频次:
count = 1;
pre->val == cur->val
:此时对于当前值的计数源自递增:
count++;
pre->val != cur->val
:此时当前值已经更新,需要重置count计数
count = 1;
每次更新count计数后,我们需要将其与maxCount进行比较:
if (count == maxCount) {
res.push_back(cur->val);
}
if (count > maxCount) {
// 刷新maxCount
maxCount = count;
// 之前的所有结果都会被删除
// 包括破纪录的数值本身也会先清除后再插入(我杀我自己)
res.clear();
res.push_back(cur->val);
}
如果数值与maxCount相等,则可能是频率并列第一的数值,便临时将其添加进结果集中。
如果数值与maxCount不相等,那说明之前的maxCount并不是真正的最高频次,需要清空已有的结果集。再将目前最高频词对应的数值填写进结果集中。
因为当前结果集也经历过
count == maxCount
的阶段,所以会出现当前val被一并清空又重新填入的清空,我删我自己:)。
完整代码如下:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
int count;
int maxCount;
vector<int> res;
TreeNode* pre;
// pre用于记录前一个结点,用于数值比较和计数
void searchBST(TreeNode* cur) {
// 先设置递归终止条件
if (cur == nullptr) return;
// 中序遍历
searchBST(cur->left);
// 处理当前节点
if (pre == nullptr) {
// 说明当前是根节点
count = 1;
} else if (pre->val == cur->val) {
// 临近节点值相同,原子递增
count++;
} else {
// 临界节点值不同,重新进行计数
count = 1;
}
pre = cur;
// 计数后与maxcount进行比较
if (count == maxCount) {
res.push_back(cur->val);
}
if (count > maxCount) {
// 刷新maxCount
maxCount = count;
// 之前的所有结果都会被删除
// 包括破纪录的数值本身也会先清除后再插入(我杀我自己)
res.clear();
res.push_back(cur->val);
}
searchBST(cur->right);
}
public:
vector<int> findMode(TreeNode* root) {
if (root == nullptr) return res;
searchBST(root);
return res;
}
};
以上是脚本宝典为你收集整理的206. 反转链表(C++)全部内容,希望文章能够帮你解决206. 反转链表(C++)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。