文章目錄

• • 1. 題目
  • 2. 中序遍歷

1. 題目

給定一個有相同值的二叉搜索樹（BST），找出 BST 中的所有眾數(shù)（出現(xiàn)頻率最高的元素）。

假定 BST 有如下定義：

結(jié)點左子樹中所含結(jié)點的值小于等于當(dāng)前結(jié)點的值
結(jié)點右子樹中所含結(jié)點的值大于等于當(dāng)前結(jié)點的值
左子樹和右子樹都是二叉搜索樹

例如： 給定 BST [1,null,2,2],1\2/2 返回[2].提示：如果眾數(shù)超過1個，不需考慮輸出順序

進(jìn)階：你可以不使用額外的空間嗎？（假設(shè)由遞歸產(chǎn)生的隱式調(diào)用棧的開銷不被計算在內(nèi)）

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 中序遍歷

• 二叉搜索樹中序遍歷是非降的，每次跟前面的比較即可，記錄最大長度
• 采用中序遍歷的循環(huán)寫法
• 具體邏輯，見代碼

class Solution { public:vector<int> findMode(TreeNode* root) {stack<TreeNode*> stk;TreeNode *tp;vector<int> 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)//只進(jìn)來一次{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);//頻率相同的都進(jìn)去}else//與前一個不相等{prev = tp->val;curlen = 1;if(curlen == maxlen)//curlen只可能==maxlen為1的情況ans.push_back(tp->val);}}return ans;} };

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的LeetCode 501. 二叉搜索树中的众数（中序遍历）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。