二叉树:求搜索树中的众数( 三 )

迭代法只要把中序遍历转成迭代 , 中间节点的处理逻辑完全一样 。
二叉树前中后序转迭代 , 传送门:

  • 二叉树:听说递归能做的 , 栈也能做
  • 二叉树:前中后序迭代方式的写法就不能统一一下么?
下面我给出其中的一种中序遍历的迭代法 , 其中间处理逻辑一点都没有变(我从递归法直接粘过来的代码 , 连注释都没改 , 哈哈)
代码如下:
class Solution {public:vector findMode(TreeNode* root) {stack st;TreeNode* cur = root;TreeNode* pre = NULL;int maxCount = 0; // 最大频率int count = 0; // 统计频率vector 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;}};总结本题在递归法中 , 我给出了如果是普通二叉树 , 应该怎么求众数 。
知道了普通二叉树的做法时候 , 我再进一步给出二叉搜索树又应该怎么求众数 , 这样鲜明的对比 , 相信会对二叉树又有更深层次的理解了 。
在递归遍历二叉搜索树的过程中 , 我还介绍了一个统计最高出现频率元素集合的技巧 ,要不然就要遍历两次二叉搜索树才能把这个最高出现频率元素的集合求出来 。
为什么没有这个技巧一定要遍历两次呢?因为要求的是集合 , 会有多个众数 , 如果规定只有一个众数 , 那么就遍历一次稳稳的了 。
最后我依然给出对应的迭代法 , 其实就是迭代法中序遍历的模板加上递归法中中间节点的处理逻辑 , 分分钟就可以写出来 , 中间逻辑的代码我都是从递归法中直接粘过来的 。
求二叉搜索树中的众数其实是一道简单题 , 但大家可以发现我写了这么一大篇幅的文章来讲解 , 主要是为了尽量从各个角度对本题进剖析 , 帮助大家更快更深入理解二叉树
「就酱 , 如果学到了的话 , 就转发给身边需要的同学吧 , 可能他们也需要!」
-------end-------
我将算法学习相关的资料已经整理到了
Github : , 里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图 , 可以fork到自己仓库有空看一看一定会有所收获 , 顺便给一个star支持一下吧!
我是程序员Carl , 哈工大师兄 , 先后在腾讯和百度打杂 , 这里每天8:35准时推送一道经典算法题目 , 我选择的每道题目都不是孤立的 , 而是由浅入深 , 环环相扣 , 帮你梳理算法知识脉络 , 轻松学算法!
@代码随想录 期待你的关注