日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

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

創(chuàng)新互聯(lián)是專業(yè)的北海網(wǎng)站建設(shè)公司，北海接單;提供網(wǎng)站設(shè)計制作、成都做網(wǎng)站,網(wǎng)頁設(shè)計,網(wǎng)站設(shè)計,建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行北海網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團隊,希望更多企業(yè)前來合作!

在求眾數(shù)集合的時候有一個技巧，因為題目中眾數(shù)是可以有多個的，所以一般的方法需要遍歷兩遍才能求出眾數(shù)的集合。

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

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

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

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

假定 BST 有如下定義：

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

例如：

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

返回[2].

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

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

思路

這道題目呢，遞歸法我從兩個維度來講。

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

遞歸法

如果不是二叉搜索樹

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

具體步驟如下：

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

至于用前中后序那種遍歷也不重要，因為就是要全遍歷一遍，怎么個遍歷法都行，層序遍歷都沒毛病!

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

 
 
 
 

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

把統(tǒng)計的出來的出現(xiàn)頻率(即map中的value)排個序

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

所以要把map轉(zhuǎn)化數(shù)組即vector，再進(jìn)行排序，當(dāng)然vector里面放的也是pair

代碼如下：

 
 
 
 

  
  
  
  
bool static cmp (const pair& a, const pair& b) { 
  
  
  
  
    return a.second > b.second; // 按照頻率從大到小排序 
  
  
  
  
} 
  
  
  
  
 
  
  
  
  
vector> vec(map.begin(), map.end()); 
  
  
  
  
sort(vec.begin(), vec.end(), cmp); // 給頻率排個序 
 
 
 
 

取前面高頻的元素

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

代碼如下：

 
 
 
 

  
  
  
  
result.push_back(vec[0].first); 
  
  
  
  
for (int i = 1; i < vec.size(); i++) { 
  
  
  
  
    // 取最高的放到result數(shù)組中 
  
  
  
  
    if (vec[i].second == vec[0].second) result.push_back(vec[i].first); 
  
  
  
  
    else break; 
  
  
  
  
} 
  
  
  
  
return result; 
 
 
 
 

整體C++代碼如下：

 
 
 
 

  
  
  
  
class Solution { 
  
  
  
  
private: 
  
  
  
  
 
  
  
  
  
void searchBST(TreeNode* cur, unordered_map& map) { // 前序遍歷 
  
  
  
  
    if (cur == NULL) return ; 
  
  
  
  
    map[cur->val]++; // 統(tǒng)計元素頻率 
  
  
  
  
    searchBST(cur->left, map); 
  
  
  
  
    searchBST(cur->right, map); 
  
  
  
  
    return ; 
  
  
  
  
} 
  
  
  
  
bool static cmp (const pair& a, const pair& b) { 
  
  
  
  
    return a.second > b.second; 
  
  
  
  
} 
  
  
  
  
public: 
  
  
  
  
    vector findMode(TreeNode* root) { 
  
  
  
  
        unordered_map map; // key:元素，value:出現(xiàn)頻率 
  
  
  
  
        vector result; 
  
  
  
  
        if (root == NULL) return result; 
  
  
  
  
        searchBST(root, map); 
  
  
  
  
        vector> vec(map.begin(), map.end()); 
  
  
  
  
        sort(vec.begin(), vec.end(), cmp); // 給頻率排個序 
  
  
  
  
        result.push_back(vec[0].first); 
  
  
  
  
        for (int i = 1; i < vec.size(); i++) { 
  
  
  
  
            // 取最高的放到result數(shù)組中 
  
  
  
  
            if (vec[i].second == vec[0].second) result.push_back(vec[i].first); 
  
  
  
  
            else break; 
  
  
  
  
        } 
  
  
  
  
        return result; 
  
  
  
  
    } 
  
  
  
  
}; 
 
 
 
 

所以如果本題沒有說是二叉搜索樹的話，那么就按照上面的思路寫!

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

如圖：

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

中序遍歷代碼如下：

 
 
 
 

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

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

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

這就考察對樹的操作了。

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

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

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

代碼如下：

 
 
 
 

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

此時又有問題了，因為要求最大頻率的元素集合(注意是集合，不是一個元素，可以有多個眾數(shù))，如果是數(shù)組上大家一般怎么辦?

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

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

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

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

那么如何只遍歷一遍呢?

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

 
 
 
 

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

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

所以下面要做如下操作：

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

 
 
 
 

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

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

 
 
 
 

  
  
  
  
class Solution { 
  
  
  
  
private: 
  
  
  
  
    int maxCount; // 最大頻率 
  
  
  
  
    int count; // 統(tǒng)計頻率 
  
  
  
  
    TreeNode* pre; 
  
  
  
  
    vector result; 
  
  
  
  
    void searchBST(TreeNode* cur) { 
  
  
  
  
        if (cur == NULL) return ; 
  
  
  
  
 
  
  
  
  
        searchBST(cur->left);       // 左 
  
  
  
  
                                    // 中 
  
  
  
  
        if (pre == NULL) { // 第一個節(jié)點 
  
  
  
  
            count = 1; 
  
  
  
  
        } else if (pre->val == cur->val) { // 與前一個節(jié)點數(shù)值相同 
  
  
  
  
            count++; 
  
  
  
  
        } else { // 與前一個節(jié)點數(shù)值不同 
  
  
  
  
            count = 1; 
  
  
  
  
        } 
  
  
  
  
        pre = cur; // 更新上一個節(jié)點 
  
  
  
  
 
  
  
  
  
        if (count == maxCount) { // 如果和最大值相同，放進(jìn)result中 
  
  
  
  
            result.push_back(cur->val); 
  
  
  
  
        } 
  
  
  
  
 
  
  
  
  
        if (count > maxCount) { // 如果計數(shù)大于最大值頻率 
  
  
  
  
            maxCount = count;   // 更新最大頻率 
  
  
  
  
            result.clear();     // 很關(guān)鍵的一步，不要忘記清空result，之前result里的元素都失效了 
  
  
  
  
            result.push_back(cur->val); 
  
  
  
  
        } 
  
  
  
  
 
  
  
  
  
        searchBST(cur->right);      // 右 
  
  
  
  
        return ; 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
public: 
  
  
  
  
    vector findMode(TreeNode* root) { 
  
  
  
  
        count = 0; 
  
  
  
  
        maxCount = 0; 
  
  
  
  
        TreeNode* pre = NULL; // 記錄前一個節(jié)點 
  
  
  
  
        result.clear(); 
  
  
  
  
 
  
  
  
  
        searchBST(root); 
  
  
  
  
        return result; 
  
  
  
  
    } 
  
  
  
  
}; 
 
 
 
 

迭代法

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

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

• 二叉樹：前中后序迭代法
• 二叉樹：前中后序統(tǒng)一風(fēng)格的迭代方式

下面我給出其中的一種中序遍歷的迭代法，其中間處理邏輯一點都沒有變(我從遞歸法直接粘過來的代碼，連注釋都沒改，哈哈)

代碼如下：

 
 
 
 

  
  
  
  
class Solution { 
  
  
  
  
public: 
  
  
  
  
    vector findMode(TreeNode* root) { 
  
  
  
  
        stack st; 
  
  
  
  
        TreeNode* cur = root; 
  
  
  
  
        TreeNode* pre = NULL; 
  
  
  
  
        int maxCount = 0; // 最大頻率 
  
  
  
  
        int count = 0; // 統(tǒng)計頻率 
  
  
  
  
        vector result; 
  
  
  
  
        while (cur != NULL || !st.empty()) { 
  
  
  
  
            if (cur != NULL) { // 指針來訪問節(jié)點，訪問到最底層 
  
  
  
  
                st.push(cur); // 將訪問的節(jié)點放進(jìn)棧 
  
  
  
  
                cur = cur->left;                // 左 
  
  
  
  
            } else { 
  
  
  
  
                cur = st.top(); 
  
  
  
  
                st.pop();                       // 中 
  
  
  
  
                if (pre == NULL) { // 第一個節(jié)點 
  
  
  
  
                    count = 1; 
  
  
  
  
                } else if (pre->val == cur->val) { // 與前一個節(jié)點數(shù)值相同 
  
  
  
  
                    count++; 
  
  
  
  
                } else { // 與前一個節(jié)點數(shù)值不同 
  
  
  
  
                    count = 1; 
  
  
  
  
                } 
  
  
  
  
                if (count == maxCount) { // 如果和最大值相同，放進(jìn)result中 
  
  
  
  
                    result.push_back(cur->val); 
  
  
  
  
                } 
  
  
  
  
 
  
  
  
  
                if (count > maxCount) { // 如果計數(shù)大于最大值頻率 
  
  
  
  
                    maxCount = count;   // 更新最大頻率 
  
  
  
  
                    result.clear();     // 很關(guān)鍵的一步，不要忘記清空result，之前result里的元素都失效了 
  
  
  
  
                    result.push_back(cur->val); 
  
  
  
  
                } 
  
  
  
  
                pre = cur; 
  
  
  
  
                cur = cur->right;               // 右 
  
  
  
  
            } 
  
  
  
  
        } 
  
  
  
  
        return result; 
  
  
  
  
    } 
  
  
  
  
}; 
 
 
 
 

總結(jié)

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

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

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

為什么沒有這個技巧一定要遍歷兩次呢?因為要求的是集合，會有多個眾數(shù)，如果規(guī)定只有一個眾數(shù)，那么就遍歷一次穩(wěn)穩(wěn)的了。

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

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

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

其他語言版本

Java

暴力法

 
 
 
 

  
  
  
  
class Solution { 
  
  
  
  
 public int[] findMode(FindModeInBinarySearchTree.TreeNode root) { 
  
  
  
  
  Map map = new HashMap<>(); 
  
  
  
  
  List list = new ArrayList<>(); 
  
  
  
  
  if (root == null) return list.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 (int i = 1; i < mapList.size(); i++) { 
  
  
  
  
   if (mapList.get(i).getValue() == mapList.get(i - 1).getValue()) { 
  
  
  
  
    list.add(mapList.get(i).getKey()); 
  
  
  
  
   } else { 
  
  
  
  
    break; 
  
  
  
  
   } 
  
  
  
  
  } 
  
  
  
  
  return list.stream().mapToInt(Integer::intValue).toArray(); 
  
  
  
  
 } 
  
  
  
  
 
  
  
  
  
 void searchBST(FindModeInBinarySearchTree.TreeNode curr, Map map) { 
  
  
  
  
  if (curr == null) return; 
  
  
  
  
  map.put(curr.val, map.getOrDefault(curr.val, 0) + 1); 
  
  
  
  
  searchBST(curr.left, map); 
  
  
  
  
  searchBST(curr.right, map); 
  
  
  
  
 } 
  
  
  
  
 
  
  
  
  
} 
 
 
 
 

 
 
 
 

  
  
  
  
class Solution { 
  
  
  
  
    ArrayList resList; 
  
  
  
  
    int maxCount; 
  
  
  
  
    int count; 
  
  
  
  
    TreeNode pre; 
  
  
  
  
 
  
  
  
  
    public int[] findMode(TreeNode root) { 
  
  
  
  
        resList = new ArrayList<>(); 
  
  
  
  
        maxCount = 0; 
  
  
  
  
        count = 0; 
  
  
  
  
        pre = null; 
  
  
  
  
        findMode1(root); 
  
  
  
  
        int[] res = new int[resList.size()]; 
  
  
  
  
        for (int i = 0; i < resList.size(); i++) { 
  
  
  
  
            res[i] = resList.get(i); 
  
  
  
  
        } 
  
  
  
  
        return res; 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
    public void findMode1(TreeNode root) { 
  
  
  
  
        if (root == null) { 
  
  
  
  
            return; 
  
  
  
  
        } 
  
  
  
  
        findMode1(root.left); 
  
  
  
  
 
  
  
  
  
        int rootValue = root.val; 
  
  
  
  
        // 計數(shù) 
  
  
  
  
        if (pre == null || rootValue != pre.val) { 
  
  
  
  
            count = 1; 
  
  
  
  
        } else { 
  
  
  
  
            count++; 
  
  
  
  
        } 
  
  
  
  
        // 更新結(jié)果以及maxCount 
  
  
  
  
        if (count > maxCount) { 
  
  
  
  
            resList.clear(); 
  
  
  
  
            resList.add(rootValue); 
  
  
  
  
            maxCount = count; 
  
  
  
  
        } else if (count == maxCount) { 
  
  
  
  
            resList.add(rootValue); 
  
  
  
  
        } 
  
  
  
  
        pre = root; 
  
  
  
  
 
  
  
  
  
        findMode1(root.right); 
  
  
  
  
    } 
  
  
  
  
} 
 
 
 
 

Python

遞歸法

 
 
 
 

  
  
  
  
class Solution: 
  
  
  
  
    def findMode(self, root: TreeNode) -> List[int]: 
  
  
  
  
        if not root: return 
  
  
  
  
        self.pre = root 
  
  
  
  
        self.count = 0   //統(tǒng)計頻率 
  
  
  
  
        self.countMax = 0  //最大頻率 
  
  
  
  
        self.res = [] 
  
  
  
  
        def findNumber(root): 
  
  
  
  
            if not root: return None  // 第一個節(jié)點 
  
  
  
  
            findNumber(root.left)  //左 
  
  
  
  
            if self.pre.val == root.val:  //中: 與前一個節(jié)點數(shù)值相同 
  
  
  
  
                self.count += 1 
  
  
  
  
            else:  // 與前一個節(jié)點數(shù)值不同 
  
  
  
  
                self.pre = root 
  
  
  
  
                self.count = 1 
  
  
  
  
            if self.count > self.countMax:  // 如果計數(shù)大于最大值頻率 
  
  
  
  
                self.countMax = self.count  // 更新最大頻率 
  
  
  
  
                self.res = [root.val]  //更新res 
  
  
  
  
            elif self.count == self.countMax:  // 如果和最大值相同，放進(jìn)res中 
  
  
  
  
                self.res.append(root.val) 
  
  
  
  
            findNumber(root.right)  //右 
  
  
  
  
            return 
  
  
  
  
        findNumber(root) 
  
  
  
  
        return self.res 
 
 
 
 

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

 
 
 
 

  
  
  
  
class Solution: 
  
  
  
  
    def findMode(self, root: TreeNode) -> List[int]: 
  
  
  
  
        stack = [] 
  
  
  
  
        cur = root 
  
  
  
  
        pre = None 
  
  
  
  
        maxCount, count = 0, 0 
  
  
  
  
        res = [] 
  
  
  
  
        while cur or stack: 
  
  
  
  
            if cur:  # 指針來訪問節(jié)點，訪問到最底層 
  
  
  
  
                stack.append(cur) 
  
  
  
  
                cur = cur.left 
  
  
  
  
            else:  # 逐一處理節(jié)點 
  
  
  
  
                cur = stack.pop() 
  
  
  
  
                if pre == None:  # 第一個節(jié)點 
  
  
  
  
                    count = 1 
  
  
  
  
                elif pre.val == cur.val:  # 與前一個節(jié)點數(shù)值相同 
  
  
  
  
                    count += 1 
  
  
  
  
                else: 
  
  
  
  
                    count = 1 
  
  
  
  
                if count == maxCount: 
  
  
  
  
                    res.append(cur.val) 
  
  
  
  
                if count > maxCount: 
  
  
  
  
                    maxCount = count 
  
  
  
  
                    res.clear() 
  
  
  
  
                    res.append(cur.val) 
  
  
  
  
 
  
  
  
  
                pre = cur 
  
  
  
  
                cur = cur.right 
  
  
  
  
        return res  
 
 
 
 

當(dāng)前文章：聊聊二叉搜索樹中的眾數(shù)是多少？
文章位置：http://www.dlmjj.cn/article/dhggjhe.html