mvc5 web網(wǎng)站開(kāi)發(fā)實(shí)戰(zhàn)廣州百度seo優(yōu)化排名
👨?💻博客主頁(yè):@花無(wú)缺
歡迎 點(diǎn)贊👍 收藏? 留言📝 加關(guān)注?!
本文由 花無(wú)缺 原創(chuàng)收錄于專(zhuān)欄 【力扣題解】
文章目錄
- 【力扣題解】P501-二叉搜索樹(shù)中的眾數(shù)-Java題解
- 🌏題目描述
- 💡題解
- 🌏總結(jié)
【力扣題解】P501-二叉搜索樹(shù)中的眾數(shù)-Java題解
P501-二叉搜索樹(shù)中的眾數(shù)
🌏題目描述
給你一個(gè)含重復(fù)值的二叉搜索樹(shù)(BST)的根節(jié)點(diǎn) root
,找出并返回 BST 中的所有 眾數(shù)(即,出現(xiàn)頻率最高的元素)。
如果樹(shù)中有不止一個(gè)眾數(shù),可以按 任意順序 返回。
假定 BST 滿(mǎn)足如下定義:
- 結(jié)點(diǎn)左子樹(shù)中所含節(jié)點(diǎn)的值 小于等于 當(dāng)前節(jié)點(diǎn)的值
- 結(jié)點(diǎn)右子樹(shù)中所含節(jié)點(diǎn)的值 大于等于 當(dāng)前節(jié)點(diǎn)的值
- 左子樹(shù)和右子樹(shù)都是二叉搜索樹(shù)
示例 1:
輸入:root = [1,null,2,2]
輸出:[2]
示例 2:
輸入:root = [0]
輸出:[0]
提示:
- 樹(shù)中節(jié)點(diǎn)的數(shù)目在范圍
[1, 104]
內(nèi) -105 <= Node.val <= 105
💡題解
遞歸:
// 節(jié)點(diǎn)值的最大出現(xiàn)頻率
int maxCount = Integer.MIN_VALUE;
// 統(tǒng)計(jì)頻率
int count = 0;
List<Integer> res = new LinkedList<>();
// 保存上一個(gè)遍歷的節(jié)點(diǎn)
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é)點(diǎn)是第一個(gè)節(jié)點(diǎn), count 為 1if (pre == null) {count = 1;// 當(dāng)前節(jié)點(diǎn)和前一個(gè)節(jié)點(diǎn)值相同, count++} else if (pre.val == root.val) {count++;// 當(dāng)前節(jié)點(diǎn)和前一個(gè)節(jié)點(diǎn)不同, count 變?yōu)?1} else {count = 1;}// 更新 pre 節(jié)點(diǎn)pre = root;// 如果當(dāng)前統(tǒng)計(jì)到的節(jié)點(diǎn)值次數(shù)和最大節(jié)點(diǎn)值次數(shù)相同// 就放入列表 resif (count == maxCount) {res.add(root.val);}// 如果 count > maxCount, 那么就更新 maxCount// 然后先清空 res, 再將當(dāng)前節(jié)點(diǎn)值加入列表 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é)點(diǎn)值的最大出現(xiàn)頻率int maxCount = Integer.MIN_VALUE;// 統(tǒng)計(jì)頻率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é)點(diǎn)是第一個(gè)節(jié)點(diǎn), count 為 1if (pre == null) {count = 1;// 當(dāng)前節(jié)點(diǎn)和前一個(gè)節(jié)點(diǎn)值相同, count++} else if (pre.val == cur.val) {count++;// 當(dāng)前節(jié)點(diǎn)和前一個(gè)節(jié)點(diǎn)不同, count 變?yōu)?1} else {count = 1;}// 更新 pre 節(jié)點(diǎn)pre = cur;// 如果當(dāng)前統(tǒng)計(jì)到的節(jié)點(diǎn)值次數(shù)和最大節(jié)點(diǎn)值次數(shù)相同// 就放入列表 resif (count == maxCount) {res.add(cur.val);}// 如果 count > maxCount, 那么就更新 maxCount// 然后先清空 res, 再將當(dāng)前節(jié)點(diǎn)值加入列表 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;
}
時(shí)間復(fù)雜度:O(n)
,需要遍歷二叉搜索樹(shù)的所有節(jié)點(diǎn),節(jié)點(diǎn)數(shù)為 n。
🌏總結(jié)
這個(gè)題要求我們查找二叉搜索樹(shù)中的眾數(shù),也就是出現(xiàn)次數(shù)最多的一個(gè)或者多個(gè)節(jié)點(diǎn)值,按照一般的做法,我們會(huì)將二叉搜索樹(shù)的節(jié)點(diǎn)值放到一個(gè)數(shù)組中,對(duì)數(shù)組進(jìn)行排序,然后使用雙指針遍歷來(lái)獲取數(shù)組中的眾數(shù),但是此題我們可以直接在遍歷的過(guò)程中獲取眾數(shù),為什么呢?因?yàn)楦鶕?jù)二叉搜索樹(shù)的特性,我們知道二叉搜索樹(shù)的中序序列是一個(gè)有序的遞增序列,所以我們可以在中序遍歷二叉搜索樹(shù)的時(shí)候同時(shí)對(duì)節(jié)點(diǎn)進(jìn)行操作,從而獲取到眾數(shù)。
同樣,在處理節(jié)點(diǎn)時(shí),我們采用雙指針?lè)?#xff0c;pre 指向上一個(gè)遍歷過(guò)的節(jié)點(diǎn),然后使用當(dāng)前節(jié)點(diǎn)和 pre 指向的節(jié)點(diǎn)進(jìn)行比較,如果相等,則統(tǒng)計(jì)變量 count++,否則重置為 1,當(dāng)然要注意,當(dāng)我們遍歷第一個(gè)節(jié)點(diǎn)的時(shí)候,pre 為 null,這時(shí)候 count 也為 1,也就是當(dāng)前節(jié)點(diǎn)出現(xiàn)了一次。
然后每一次遍歷之后,我們要將當(dāng)前節(jié)點(diǎn)頻次 count 和最大頻次 maxCount 作比較,只要相等,就將當(dāng)前節(jié)點(diǎn)值加入結(jié)果列表 res,但是有可能當(dāng)前節(jié)點(diǎn)的頻次還會(huì)增多,這怎么辦呢?這就要到一下步驟了,如果當(dāng)前頻次 count 大于 maxCount,那么就更新 maxCount,接著我們要清空 res,這樣就避免了出現(xiàn)錯(cuò)誤結(jié)果的情況,然后將當(dāng)前節(jié)點(diǎn)值加入 res。
以上我也給出了迭代法的代碼,和遞歸代碼的邏輯是完全一樣的。
作者:花無(wú)缺(huawuque404.com)
🌸歡迎
關(guān)注
我的博客:花無(wú)缺-每一個(gè)不曾起舞的日子都是對(duì)生命的辜負(fù)~
🍻一起進(jìn)步-刷題專(zhuān)欄:【力扣題解】
🥇往期精彩好文:
📢【全網(wǎng)最全愛(ài)心代碼倉(cāng)庫(kù)】
📢【CSS選擇器全解指南】
📢【HTML萬(wàn)字詳解】
你們的點(diǎn)贊👍 收藏? 留言📝 關(guān)注?
是我持續(xù)創(chuàng)作,輸出優(yōu)質(zhì)內(nèi)容
的最大動(dòng)力!
謝謝!