二叉樹上應(yīng)該怎么求，二叉搜索樹上又應(yīng)該怎么求？

在求眾數(shù)集合的時(shí)候有一個(gè)技巧，因?yàn)轭}目中眾數(shù)是可以有多個(gè)的，所以一般的方法需要遍歷兩遍才能求出眾數(shù)的集合。

但可以遍歷一遍就可以求眾數(shù)集合，使用了適時(shí)清空結(jié)果集的方法，這個(gè)方法還是很巧妙的。相信仔細(xì)讀了文章的同學(xué)會(huì)驚呼其巧妙！

501.二叉搜索樹中的眾數(shù)

題目鏈接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/solution

給定一個(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)的值
左子樹和右子樹都是二叉搜索樹

例如：

給定 BST [1,null,2,2],

返回[2].

提示：如果眾數(shù)超過(guò)1個(gè)，不需考慮輸出順序

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

思路

這道題目呢，遞歸法我從兩個(gè)維度來(lái)講。

首先如果不是二叉搜索樹的話，應(yīng)該怎么解題，是二叉搜索樹，又應(yīng)該如何解題，兩種方式做一個(gè)比較，可以加深大家對(duì)二叉樹的理解。

遞歸法

如果不是二叉搜索樹

如果不是二叉搜索樹，最直觀的方法一定是把這個(gè)樹都遍歷了，用map統(tǒng)計(jì)頻率，把頻率排個(gè)序，最后取前面高頻的元素的集合。

具體步驟如下：

這個(gè)樹都遍歷了，用map統(tǒng)計(jì)頻率

至于用前中后序那種遍歷也不重要，因?yàn)榫褪且闅v一遍，怎么個(gè)遍歷法都行，層序遍歷都沒(méi)毛??！

這里采用前序遍歷，代碼如下：

//mapkey:元素，value:出現(xiàn)頻率
voidsearchBST(TreeNode*cur,unordered_map<int,int>&map){//前序遍歷
if(cur==NULL)return;
map[cur->val]++;//統(tǒng)計(jì)元素頻率
searchBST(cur->left,map);
searchBST(cur->right,map);
return;
}

把統(tǒng)計(jì)的出來(lái)的出現(xiàn)頻率（即map中的value）排個(gè)序

有的同學(xué)可能可以想直接對(duì)map中的value排序，還真做不到，C++中如果使用std::map或者std::multimap可以對(duì)key排序，但不能對(duì)value排序。

所以要把map轉(zhuǎn)化數(shù)組即vector，再進(jìn)行排序，當(dāng)然vector里面放的也是pair類型的數(shù)據(jù)，第一個(gè)int為元素，第二個(gè)int為出現(xiàn)頻率。

代碼如下：

boolstaticcmp(constpair&a,constpair&b){
returna.second>b.second;//按照頻率從大到小排序
}

vector>vec(map.begin(),map.end());
sort(vec.begin(),vec.end(),cmp);//給頻率排個(gè)序

取前面高頻的元素

此時(shí)數(shù)組vector中已經(jīng)是存放著按照頻率排好序的pair，那么把前面高頻的元素取出來(lái)就可以了。

代碼如下：

result.push_back(vec[0].first);
for(inti=1;i//取最高的放到result數(shù)組中
if(vec[i].second==vec[0].second)result.push_back(vec[i].first);
elsebreak;
}
returnresult;

整體C++代碼如下：

classSolution{
private:

voidsearchBST(TreeNode*cur,unordered_map<int,int>&map){//前序遍歷
if(cur==NULL)return;
map[cur->val]++;//統(tǒng)計(jì)元素頻率
searchBST(cur->left,map);
searchBST(cur->right,map);
return;
}
boolstaticcmp(constpair<int,int>&a,constpair<int,int>&b){
returna.second>b.second;
}
public:
vector<int>findMode(TreeNode*root){
unordered_map<int,int>map;//key:元素，value:出現(xiàn)頻率
vector<int>result;
if(root==NULL)returnresult;
searchBST(root,map);
vectorint,int>>vec(map.begin(),map.end());
sort(vec.begin(),vec.end(),cmp);//給頻率排個(gè)序
result.push_back(vec[0].first);
for(inti=1;i//取最高的放到result數(shù)組中
if(vec[i].second==vec[0].second)result.push_back(vec[i].first);
elsebreak;
}
returnresult;
}
};

所以如果本題沒(méi)有說(shuō)是二叉搜索樹的話，那么就按照上面的思路寫！

是二叉搜索樹

既然是搜索樹，它中序遍歷就是有序的。

中序遍歷代碼如下：

voidsearchBST(TreeNode*cur){
if(cur==NULL)return;
searchBST(cur->left);//左
（處理節(jié)點(diǎn)）//中
searchBST(cur->right);//右
return;
}

遍歷有序數(shù)組的元素出現(xiàn)頻率，從頭遍歷，那么一定是相鄰兩個(gè)元素作比較，然后就把出現(xiàn)頻率最高的元素輸出就可以了。

關(guān)鍵是在有序數(shù)組上的話，好搞，在樹上怎么搞呢？

這就考察對(duì)樹的操作了。

在二叉樹：搜索樹的最小絕對(duì)差中我們就使用了pre指針和cur指針的技巧，這次又用上了。

弄一個(gè)指針指向前一個(gè)節(jié)點(diǎn)，這樣每次cur（當(dāng)前節(jié)點(diǎn)）才能和pre（前一個(gè)節(jié)點(diǎn)）作比較。

而且初始化的時(shí)候pre = NULL，這樣當(dāng)pre為NULL時(shí)候，我們就知道這是比較的第一個(gè)元素。

代碼如下：

if(pre==NULL){//第一個(gè)節(jié)點(diǎn)
count=1;//頻率為1
}elseif(pre->val==cur->val){//與前一個(gè)節(jié)點(diǎn)數(shù)值相同
count++;
}else{//與前一個(gè)節(jié)點(diǎn)數(shù)值不同
count=1;
}
pre=cur;//更新上一個(gè)節(jié)點(diǎn)

此時(shí)又有問(wèn)題了，因?yàn)橐笞畲箢l率的元素集合（注意是集合，不是一個(gè)元素，可以有多個(gè)眾數(shù)），如果是數(shù)組上大家一般怎么辦？

應(yīng)該是先遍歷一遍數(shù)組，找出最大頻率（maxCount），然后再重新遍歷一遍數(shù)組把出現(xiàn)頻率為maxCount的元素放進(jìn)集合。（因?yàn)楸姅?shù)有多個(gè)）

這種方式遍歷了兩遍數(shù)組。

那么我們遍歷兩遍二叉搜索樹，把眾數(shù)集合算出來(lái)也是可以的。

但這里其實(shí)只需要遍歷一次就可以找到所有的眾數(shù)。

那么如何只遍歷一遍呢？

如果頻率count 等于 maxCount（最大頻率），當(dāng)然要把這個(gè)元素加入到結(jié)果集中（以下代碼為result數(shù)組），代碼如下：

if(count==maxCount){//如果和最大值相同，放進(jìn)result中
result.push_back(cur->val);
}

是不是感覺(jué)這里有問(wèn)題，result怎么能輕易就把元素放進(jìn)去了呢，萬(wàn)一，這個(gè)maxCount此時(shí)還不是真正最大頻率呢。

所以下面要做如下操作：

頻率count 大于 maxCount的時(shí)候，不僅要更新maxCount，而且要清空結(jié)果集（以下代碼為result數(shù)組），因?yàn)榻Y(jié)果集之前的元素都失效了。

if(count>maxCount){//如果計(jì)數(shù)大于最大值
maxCount=count;//更新最大頻率
result.clear();//很關(guān)鍵的一步，不要忘記清空result，之前result里的元素都失效了
result.push_back(cur->val);
}

關(guān)鍵代碼都講完了，完整代碼如下：（只需要遍歷一遍二叉搜索樹，就求出了眾數(shù)的集合）

classSolution{
private:
intmaxCount;//最大頻率
intcount;//統(tǒng)計(jì)頻率
TreeNode*pre;
vector<int>result;
voidsearchBST(TreeNode*cur){
if(cur==NULL)return;

searchBST(cur->left);//左
//中
if(pre==NULL){//第一個(gè)節(jié)點(diǎn)
count=1;
}elseif(pre->val==cur->val){//與前一個(gè)節(jié)點(diǎn)數(shù)值相同
count++;
}else{//與前一個(gè)節(jié)點(diǎn)數(shù)值不同
count=1;
}
pre=cur;//更新上一個(gè)節(jié)點(diǎn)

if(count==maxCount){//如果和最大值相同，放進(jìn)result中
result.push_back(cur->val);
}

if(count>maxCount){//如果計(jì)數(shù)大于最大值頻率
maxCount=count;//更新最大頻率
result.clear();//很關(guān)鍵的一步，不要忘記清空result，之前result里的元素都失效了
result.push_back(cur->val);
}

searchBST(cur->right);//右
return;
}

public:
vector<int>findMode(TreeNode*root){
count=0;
maxCount=0;
TreeNode*pre=NULL;//記錄前一個(gè)節(jié)點(diǎn)
result.clear();

searchBST(root);
returnresult;
}
};

迭代法

只要把中序遍歷轉(zhuǎn)成迭代，中間節(jié)點(diǎn)的處理邏輯完全一樣。

二叉樹前中后序轉(zhuǎn)迭代，傳送門：

下面我給出其中的一種中序遍歷的迭代法，其中間處理邏輯一點(diǎn)都沒(méi)有變（我從遞歸法直接粘過(guò)來(lái)的代碼，連注釋都沒(méi)改，哈哈）

代碼如下：

classSolution{
public:
vector<int>findMode(TreeNode*root){
stackst;
TreeNode*cur=root;
TreeNode*pre=NULL;
intmaxCount=0;//最大頻率
intcount=0;//統(tǒng)計(jì)頻率
vector<int>result;
while(cur!=NULL||!st.empty()){
if(cur!=NULL){//指針來(lái)訪問(wèn)節(jié)點(diǎn)，訪問(wèn)到最底層
st.push(cur);//將訪問(wèn)的節(jié)點(diǎn)放進(jìn)棧
cur=cur->left;//左
}else{
cur=st.top();
st.pop();//中
if(pre==NULL){//第一個(gè)節(jié)點(diǎn)
count=1;
}elseif(pre->val==cur->val){//與前一個(gè)節(jié)點(diǎn)數(shù)值相同
count++;
}else{//與前一個(gè)節(jié)點(diǎn)數(shù)值不同
count=1;
}
if(count==maxCount){//如果和最大值相同，放進(jìn)result中
result.push_back(cur->val);
}

if(count>maxCount){//如果計(jì)數(shù)大于最大值頻率
maxCount=count;//更新最大頻率
result.clear();//很關(guān)鍵的一步，不要忘記清空result，之前result里的元素都失效了
result.push_back(cur->val);
}
pre=cur;
cur=cur->right;//右
}
}
returnresult;
}
};

總結(jié)

本題在遞歸法中，我給出了如果是普通二叉樹，應(yīng)該怎么求眾數(shù)。

知道了普通二叉樹的做法時(shí)候，我再進(jìn)一步給出二叉搜索樹又應(yīng)該怎么求眾數(shù)，這樣鮮明的對(duì)比，相信會(huì)對(duì)二叉樹又有更深層次的理解了。

在遞歸遍歷二叉搜索樹的過(guò)程中，我還介紹了一個(gè)統(tǒng)計(jì)最高出現(xiàn)頻率元素集合的技巧，要不然就要遍歷兩次二叉搜索樹才能把這個(gè)最高出現(xiàn)頻率元素的集合求出來(lái)。

為什么沒(méi)有這個(gè)技巧一定要遍歷兩次呢？因?yàn)橐蟮氖羌希瑫?huì)有多個(gè)眾數(shù)，如果規(guī)定只有一個(gè)眾數(shù)，那么就遍歷一次穩(wěn)穩(wěn)的了。

最后我依然給出對(duì)應(yīng)的迭代法，其實(shí)就是迭代法中序遍歷的模板加上遞歸法中中間節(jié)點(diǎn)的處理邏輯，分分鐘就可以寫出來(lái)，中間邏輯的代碼我都是從遞歸法中直接粘過(guò)來(lái)的。

求二叉搜索樹中的眾數(shù)其實(shí)是一道簡(jiǎn)單題，但大家可以發(fā)現(xiàn)我寫了這么一大篇幅的文章來(lái)講解，主要是為了盡量從各個(gè)角度對(duì)本題進(jìn)剖析，幫助大家更快更深入理解二叉樹。

需要強(qiáng)調(diào)的是 leetcode上的耗時(shí)統(tǒng)計(jì)是非常不準(zhǔn)確的，看個(gè)大概就行，一樣的代碼耗時(shí)可以差百分之50以上，所以leetcode的耗時(shí)統(tǒng)計(jì)別太當(dāng)回事，知道理論上的效率優(yōu)劣就行了。

其他語(yǔ)言版本

Java

暴力法

classSolution{
publicint[]findMode(FindModeInBinarySearchTree.TreeNoderoot){
Mapmap=newHashMap<>();
Listlist=newArrayList<>();
if(root==null)returnlist.stream().mapToInt(Integer::intValue).toArray();
//獲得頻率Map
searchBST(root,map);
List>mapList=map.entrySet().stream()
.sorted((c1,c2)->c2.getValue().compareTo(c1.getValue()))
.collect(Collectors.toList());
list.add(mapList.get(0).getKey());
//把頻率最高的加入list
for(inti=1;iif(mapList.get(i).getValue()==mapList.get(i-1).getValue()){
list.add(mapList.get(i).getKey());
}else{
break;
}
}
returnlist.stream().mapToInt(Integer::intValue).toArray();
}

voidsearchBST(FindModeInBinarySearchTree.TreeNodecurr,Mapmap){
if(curr==null)return;
map.put(curr.val,map.getOrDefault(curr.val,0)+1);
searchBST(curr.left,map);
searchBST(curr.right,map);
}

}

classSolution{
ArrayListresList;
intmaxCount;
intcount;
TreeNodepre;

publicint[]findMode(TreeNoderoot){
resList=newArrayList<>();
maxCount=0;
count=0;
pre=null;
findMode1(root);
int[]res=newint[resList.size()];
for(inti=0;ireturnres;
}

publicvoidfindMode1(TreeNoderoot){
if(root==null){
return;
}
findMode1(root.left);

introotValue=root.val;
//計(jì)數(shù)
if(pre==null||rootValue!=pre.val){
count=1;
}else{
count++;
}
//更新結(jié)果以及maxCount
if(count>maxCount){
resList.clear();
resList.add(rootValue);
maxCount=count;
}elseif(count==maxCount){
resList.add(rootValue);
}
pre=root;

findMode1(root.right);
}
}

Python

遞歸法

classSolution:
deffindMode(self,root:TreeNode)->List[int]:
ifnotroot:return
self.pre=root
self.count=0//統(tǒng)計(jì)頻率
self.countMax=0//最大頻率
self.res=[]
deffindNumber(root):
ifnotroot:returnNone//第一個(gè)節(jié)點(diǎn)
findNumber(root.left)//左
ifself.pre.val==root.val://中:與前一個(gè)節(jié)點(diǎn)數(shù)值相同
self.count+=1
else://與前一個(gè)節(jié)點(diǎn)數(shù)值不同
self.pre=root
self.count=1
ifself.count>self.countMax://如果計(jì)數(shù)大于最大值頻率
self.countMax=self.count//更新最大頻率
self.res=[root.val]//更新res
elifself.count==self.countMax://如果和最大值相同，放進(jìn)res中
self.res.append(root.val)
findNumber(root.right)//右
return
findNumber(root)
returnself.res

迭代法-中序遍歷-不使用額外空間，利用二叉搜索樹特性

classSolution:
deffindMode(self,root:TreeNode)->List[int]:
stack=[]
cur=root
pre=None
maxCount,count=0,0
res=[]
whilecurorstack:
ifcur:#指針來(lái)訪問(wèn)節(jié)點(diǎn)，訪問(wèn)到最底層
stack.append(cur)
cur=cur.left
else:#逐一處理節(jié)點(diǎn)
cur=stack.pop()
ifpre==None:#第一個(gè)節(jié)點(diǎn)
count=1
elifpre.val==cur.val:#與前一個(gè)節(jié)點(diǎn)數(shù)值相同
count+=1
else:
count=1
ifcount==maxCount:
res.append(cur.val)
ifcount>maxCount:
maxCount=count
res.clear()
res.append(cur.val)

pre=cur
cur=cur.right
returnres

責(zé)任編輯：haq

聲明：本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場(chǎng)。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問(wèn)題，請(qǐng)聯(lián)系本站處理。舉報(bào)投訴