大淘客做自己网站,云南最大的互联网公司,建设银行网站短信错误6次,自学网设计文章目录1. 题目2. 中序遍历1. 题目
给定一个有相同值的二叉搜索树#xff08;BST#xff09;#xff0c;找出 BST 中的所有众数#xff08;出现频率最高的元素#xff09;。
假定 BST 有如下定义#xff1a;
结点左子树中所含结点的值小于等于当前结点的值 结点右子树…
文章目录1. 题目2. 中序遍历1. 题目
给定一个有相同值的二叉搜索树BST找出 BST 中的所有众数出现频率最高的元素。
假定 BST 有如下定义
结点左子树中所含结点的值小于等于当前结点的值 结点右子树中所含结点的值大于等于当前结点的值 左子树和右子树都是二叉搜索树
例如
给定 BST [1,null,2,2],1\2/2
返回[2].提示如果众数超过1个不需考虑输出顺序进阶你可以不使用额外的空间吗假设由递归产生的隐式调用栈的开销不被计算在内
来源力扣LeetCode 链接https://leetcode-cn.com/problems/find-mode-in-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 中序遍历
二叉搜索树中序遍历是非降的每次跟前面的比较即可记录最大长度采用中序遍历的循环写法具体逻辑见代码
class Solution {
public:vectorint findMode(TreeNode* root) {stackTreeNode* stk;TreeNode *tp;vectorint ans;int prev, maxlen 0, curlen 0;bool flag true;while(root || !stk.empty()){while(root){stk.push(root);root root-left;}tp stk.top();stk.pop();root tp-right;if(flag)//只进来一次{prev tp-val;flag false;curlen 1;maxlen 1;ans.push_back(tp-val);continue;}if(tp-val prev){curlen;if(curlen maxlen){ //碰见频率大的maxlen curlen;ans.clear();//清空频率小的ans.push_back(tp-val);}else if(curlen maxlen)ans.push_back(tp-val);//频率相同的都进去}else//与前一个不相等{prev tp-val;curlen 1;if(curlen maxlen)//curlen只可能maxlen为1的情况ans.push_back(tp-val);}}return ans;}
};
