👨?💻博客主頁：@花無缺
歡迎 點贊👍 收藏? 留言📝 加關(guān)注?!
本文由 花無缺 原創(chuàng)

收錄于專欄 【力扣題解】

---

---

【力扣題解】P501-二叉搜索樹中的眾數(shù)-Java題解

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

🌏題目描述

給你一個含重復(fù)值的二叉搜索樹（BST）的根節(jié)點 root ，找出并返回 BST 中的所有 眾數(shù)（即，出現(xiàn)頻率最高的元素）。

如果樹中有不止一個眾數(shù)，可以按 任意順序 返回。

假定 BST 滿足如下定義：

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

示例 1：

輸入：root = [1,null,2,2]
輸出：[2]

示例 2：

輸入：root = [0]
輸出：[0]

提示：

• 樹中節(jié)點的數(shù)目在范圍 [1, 104] 內(nèi)
• -105 <= Node.val <= 105

💡題解

遞歸：

// 節(jié)點值的最大出現(xiàn)頻率
int maxCount = Integer.MIN_VALUE;
// 統(tǒng)計頻率
int count = 0;
List<Integer> res = new LinkedList<>();
// 保存上一個遍歷的節(jié)點
TreeNode pre = null;
public int[] findMode(TreeNode root) {dfs(root);int[] a = new int[res.size()];for (int i = 0; i < a.length; i++) {a[i] = res.get(i);}return a;
}
public void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);// 當(dāng)前節(jié)點是第一個節(jié)點, count 為 1if (pre == null) {count = 1;//     當(dāng)前節(jié)點和前一個節(jié)點值相同, count++} else if (pre.val == root.val) {count++;//     當(dāng)前節(jié)點和前一個節(jié)點不同, count 變?yōu)?1} else {count = 1;}// 更新 pre 節(jié)點pre = root;// 如果當(dāng)前統(tǒng)計到的節(jié)點值次數(shù)和最大節(jié)點值次數(shù)相同// 就放入列表 resif (count == maxCount) {res.add(root.val);}// 如果 count > maxCount, 那么就更新 maxCount// 然后先清空 res, 再將當(dāng)前節(jié)點值加入列表 resif (count > maxCount) {maxCount = count;res.clear();res.add(root.val);}dfs(root.right);
}

迭代：

public int[] findMode(TreeNode root) {Deque<TreeNode> stack = new LinkedList<>();TreeNode cur = root;TreeNode pre = null;// 節(jié)點值的最大出現(xiàn)頻率int maxCount = Integer.MIN_VALUE;// 統(tǒng)計頻率int count = 0;List<Integer> res = new LinkedList<>();while (!stack.isEmpty() || cur != null) {if (cur != null) {stack.offerLast(cur);cur = cur.left;} else {cur = stack.pollLast();// 當(dāng)前節(jié)點是第一個節(jié)點, count 為 1if (pre == null) {count = 1;//     當(dāng)前節(jié)點和前一個節(jié)點值相同, count++} else if (pre.val == cur.val) {count++;//     當(dāng)前節(jié)點和前一個節(jié)點不同, count 變?yōu)?1} else {count = 1;}// 更新 pre 節(jié)點pre = cur;// 如果當(dāng)前統(tǒng)計到的節(jié)點值次數(shù)和最大節(jié)點值次數(shù)相同// 就放入列表 resif (count == maxCount) {res.add(cur.val);}// 如果 count > maxCount, 那么就更新 maxCount// 然后先清空 res, 再將當(dāng)前節(jié)點值加入列表 resif (count > maxCount) {maxCount = count;res.clear();res.add(cur.val);}cur = cur.right;}}int[] a = new int[res.size()];for (int i = 0; i < a.length; i++) {a[i] = res.get(i);}return a;
}

時間復(fù)雜度：O(n)，需要遍歷二叉搜索樹的所有節(jié)點，節(jié)點數(shù)為 n。

🌏總結(jié)

這個題要求我們查找二叉搜索樹中的眾數(shù)，也就是出現(xiàn)次數(shù)最多的一個或者多個節(jié)點值，按照一般的做法，我們會將二叉搜索樹的節(jié)點值放到一個數(shù)組中，對數(shù)組進行排序，然后使用雙指針遍歷來獲取數(shù)組中的眾數(shù)，但是此題我們可以直接在遍歷的過程中獲取眾數(shù)，為什么呢？因為根據(jù)二叉搜索樹的特性，我們知道二叉搜索樹的中序序列是一個有序的遞增序列，所以我們可以在中序遍歷二叉搜索樹的時候同時對節(jié)點進行操作，從而獲取到眾數(shù)。

同樣，在處理節(jié)點時，我們采用雙指針法，pre 指向上一個遍歷過的節(jié)點，然后使用當(dāng)前節(jié)點和 pre 指向的節(jié)點進行比較，如果相等，則統(tǒng)計變量 count++，否則重置為 1，當(dāng)然要注意，當(dāng)我們遍歷第一個節(jié)點的時候，pre 為 null，這時候 count 也為 1，也就是當(dāng)前節(jié)點出現(xiàn)了一次。

然后每一次遍歷之后，我們要將當(dāng)前節(jié)點頻次 count 和最大頻次 maxCount 作比較，只要相等，就將當(dāng)前節(jié)點值加入結(jié)果列表 res，但是有可能當(dāng)前節(jié)點的頻次還會增多，這怎么辦呢？這就要到一下步驟了，如果當(dāng)前頻次 count 大于 maxCount，那么就更新 maxCount，接著我們要清空 res，這樣就避免了出現(xiàn)錯誤結(jié)果的情況，然后將當(dāng)前節(jié)點值加入 res。

以上我也給出了迭代法的代碼，和遞歸代碼的邏輯是完全一樣的。

作者：花無缺(huawuque404.com)

---

🌸歡迎關(guān)注我的博客：花無缺-每一個不曾起舞的日子都是對生命的辜負~
🍻一起進步-刷題專欄：【力扣題解】
🥇往期精彩好文：
📢【全網(wǎng)最全愛心代碼倉庫】
📢【CSS選擇器全解指南】
📢【HTML萬字詳解】
你們的點贊👍 收藏? 留言📝 關(guān)注?
是我持續(xù)創(chuàng)作，輸出優(yōu)質(zhì)內(nèi)容的最大動力！
謝謝！