[[419638]]

二叉樹上應該怎么求，二叉搜索樹上又應該怎么求?

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

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

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

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

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

假定 BST 有如下定義：

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

例如：

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

返回[2].

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

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

思路

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

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

遞歸法

如果不是二叉搜索樹

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

具體步驟如下：

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

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

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

// map<int, int> key:元素，value:出現(xiàn)頻率 
void searchBST(TreeNode* cur, unordered_map<int, int>& 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)排個序

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

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

代碼如下：

bool static cmp (const pair<int, int>& a, const pair<int, int>& b) { 
    return a.second > b.second; // 按照頻率從大到小排序 
} 
 
vector<pair<int, int>> 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<int, int>& map) { // 前序遍歷 
    if (cur == NULL) return ; 
    map[cur->val]++; // 統(tǒng)計元素頻率 
    searchBST(cur->left, map); 
    searchBST(cur->right, map); 
    return ; 
} 
bool static cmp (const pair<int, int>& a, const pair<int, int>& b) { 
    return a.second > b.second; 
} 
public: 
    vector<int> findMode(TreeNode* root) { 
        unordered_map<int, int> map; // key:元素，value:出現(xiàn)頻率 
        vector<int> result; 
        if (root == NULL) return result; 
        searchBST(root, map); 
        vector<pair<int, int>> 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)頻率最高的元素輸出就可以了。

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

這就考察對樹的操作了。

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

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

而且初始化的時候pre = NULL，這樣當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ù)組上大家一般怎么辦?

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

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

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

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

那么如何只遍歷一遍呢?

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

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

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

所以下面要做如下操作：

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

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

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

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

迭代法

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

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

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

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

代碼如下：

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

總結(jié)

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

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

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

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

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

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

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

其他語言版本

Java

暴力法

class Solution { 
 public int[] findMode(FindModeInBinarySearchTree.TreeNode root) { 
  Map<Integer, Integer> map = new HashMap<>(); 
  List<Integer> list = new ArrayList<>(); 
  if (root == null) return list.stream().mapToInt(Integer::intValue).toArray(); 
  // 獲得頻率 Map 
  searchBST(root, map); 
  List<Map.Entry<Integer, Integer>> 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<Integer, Integer> 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<Integer> 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:  // 如果和最大值相同，放進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