目錄

• • 題目
  • 1、不考慮BTS性質(zhì)，直接尋找眾數(shù)集合（利用map）
  • 2、考慮BTS的中序遍歷結(jié)果性質(zhì)

題目

給定一個(gè)有相同值的二叉搜索樹（BST），找出 BST 中的所有眾數(shù)（出現(xiàn)頻率最高的元素）。
假定 BST 有如下定義：
結(jié)點(diǎn)左子樹中所含結(jié)點(diǎn)的值小于等于當(dāng)前結(jié)點(diǎn)的值
結(jié)點(diǎn)右子樹中所含結(jié)點(diǎn)的值大于等于當(dāng)前結(jié)點(diǎn)的值
左子樹和右子樹都是二叉搜索樹

1、不考慮BTS性質(zhì)，直接尋找眾數(shù)集合（利用map）

這種方法沒有考慮性質(zhì)，同時(shí)消耗了額外的空間。
同時(shí)要注意，按照value值排序是沒有內(nèi)置函數(shù)的，得先將map轉(zhuǎn)換為vector，然后自定義sort的規(guī)則，對pair類型數(shù)據(jù)的第二個(gè)值按照從大到小進(jìn)行排序。

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { private:void traversal(TreeNode* cur,unordered_map<int,int>& map){if(cur == NULL ) return ;//以結(jié)點(diǎn)值為key，結(jié)點(diǎn)值出現(xiàn)的頻次為map值map[cur->val]++;traversal(cur->left,map);traversal(cur->right,map);return ;}//定義sort排序的規(guī)則，以二維數(shù)組的第二維從大到小排序bool static cmp(const pair<int,int>& a,const pair<int,int>& b){if(a.second>b.second) return 1;else return 0;} public:vector<int> findMode(TreeNode* root) {unordered_map<int,int> map;vector<int> result;if(root == NULL) return result;traversal(root,map);//將map轉(zhuǎn)化為vector(二維數(shù)組)，以便于下一步的排序vector<pair<int,int>> vec(map.begin(),map.end());sort(vec.begin(),vec.end(),cmp);//vec第一個(gè)元素是頻次最高的，然后繼續(xù)尋找與之頻次一樣的元素for(int i=0;i<vec.size();i++){if(vec[i].second == vec[0].second) result.push_back(vec[i].first);else break;}return result;} };

2、考慮BTS的中序遍歷結(jié)果性質(zhì)

中序遍歷的結(jié)果是遞增的，所以我們只需要比較此結(jié)點(diǎn)與上結(jié)點(diǎn)是否相等，從而累加頻次，然后更新最大頻次，更新結(jié)果數(shù)組，保證眾數(shù)集合就行了。

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { private:int MaxCount;int count;TreeNode* pre = NULL;vector<int> result;void traversal(TreeNode* cur){if(cur == NULL ) return;traversal(cur->left);if(pre == NULL){count = 1;}else if(pre->val == cur->val){count++;}else{count = 1;}pre = cur;//如果出現(xiàn)次數(shù)也是最大次數(shù)，說明此元素也屬于眾數(shù)集合，應(yīng)當(dāng)加入結(jié)果集if(count == MaxCount) result.push_back(cur->val);//如果最大次數(shù)被更新，那么得清除舊結(jié)果if(count > MaxCount){MaxCount = count;result.clear();result.push_back(cur->val);}traversal(cur->right);return ;} public:vector<int> findMode(TreeNode* root) {MaxCount = 0;count = 0;pre = NULL;result.clear();traversal(root);return result;} };

總結(jié)

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

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