【LeetCode】第501題——二叉搜尋樹中的衆數(難度:簡單)
- 題目描述
- 解題思路
- 代碼詳解
-
- 思路一:中序周遊+HashMap
- 思路二:中序周遊(但不用記錄所有val的出現次數)
- 思路三:Morris中序周遊+思路二
- 注意點
題目描述
給定一個有相同值的二叉搜尋樹(BST),找出 BST 中的所有衆數(出現頻率最高的元素)。
假定 BST 有如下定義:
結點左子樹中所含結點的值小于等于目前結點的值
結點右子樹中所含結點的值大于等于目前結點的值
左子樹和右子樹都是二叉搜尋樹
-
示例:
輸入: BST [1,null,2,2],
輸出:[2].1 \ 2 / 2
提示:如果衆數超過1個,不需考慮輸出順序
進階:你可以不使用額外的空間嗎?(假設由遞歸産生的隐式調用棧的開銷不被計算在内)
來源:力扣(LeetCode)
連結:https://leetcode-cn.com/problems/find-mode-in-binary-search-tree
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。
解題思路
周遊方式都是基于中序周遊。
思路一:普通中序周遊,利用HashMap存儲出現過的val值和其出現次數。在HashMap中找出衆數。
思路二:普通中序周遊,利用BST的特性,中序周遊到的數字是按順序遞增的。也就是說如果目前數字等于上一個數字,則 ++count,若目前數字不等于上一數字,則count=1。然後比較count和max(max是最大出現次數)
思路三:Morris中序周遊,在加上思路二的存儲最大值思路。
這裡簡單說一下Morris中序周遊的步驟,因為樹的周遊結合動圖會更容易了解,但本人技術有限,是以具體理論不再此闡述。
- 如果cur無左子樹,cur向右移動(cur=cur.right)
- 如果cur有左子樹,找到cur左子樹上最右的節點,記為rightend
- 如果rightend的right指針指向空,讓其(rightend的right指針)指向cur,cur向左移動(cur=cur.left)
- 如果rightend的right指針指向cur,讓其(rightend的right指針)指向空,cur向右移動(cur=cur.right)
代碼詳解
思路一:中序周遊+HashMap
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
HashMap<Integer, Integer> hm;
int max = 1; // 0也可
public int[] findMode(TreeNode root) {
hm = new HashMap<>();
Stack<Integer> stack = new Stack<>(); // 利用棧來存儲複數個衆數
func(root); // 中序周遊的遞歸寫法
// 遞歸完後max也會得到,周遊HashMap的key,找到value==max的key,壓入stack中
for(int i : hm.keySet()) {
if(hm.get(i) == max) {
stack.push(i);
}
}
// stack的作用其實就是得到ints數組的長度
int[] ints = new int[stack.size()];
for(int i = 0; i < ints.length; ++i) {
ints[i] = stack.pop();
}
return ints;
}
// 這個func的作用是中序周遊+更新HashMap+更新max
public void func(TreeNode node) {
if(node != null) {
// 更新HashMap
if(hm.containsKey(node.val)) {
hm.replace(node.val, hm.get(node.val)+1);
} else {
hm.put(node.val, 1);
}
// 更新max
if(hm.get(node.val) > max) {
max = hm.get(node.val);
}
// 中序周遊
func(node.left);
func(node.right);
}
}
}
思路二:中序周遊(但不用記錄所有val的出現次數)
class Solution {
Stack<Integer> stack;
int max = 0; // 同一val出現的最大次數
int base = 1; // 上一個數,判斷目前數與上一個數是否相等,初值無所謂是多少
int count = 0; // 記錄目前數的出現次數,換了個base就得重置一遍count=1
public int[] findMode(TreeNode root) {
stack = new Stack<>();
func(root); // 中序周遊
// stack已經在func中确定了,依次指派給ints即可
int[] ints = new int[stack.size()];
for(int i = 0; i < ints.length; ++i) {
ints[i] = stack.pop();
}
return ints;
}
// 這個func的作用是中序周遊+更新count+更新base+更新max+更新stack
public void func(TreeNode node) {
if(node != null) {
// 中序周遊先是左
func(node.left);
// 中序周遊再是根
if(node.val == base) { // 目前數字和上一數字相同,則++count
++count;
} else { // 若不同則重置count=1并更改base
count = 1;
base = node.val;
}
// 若max變了,stack就得清除一遍,再壓入目前周遊的數字
if(count > max) {
max = count;
stack.clear();
stack.push(node.val);
} else if(count == max) { // 别忘了出現次數等于max的數字也需要入棧
stack.push(node.val);
}
// 中序周遊最後是右
func(node.right);
}
}
}
思路三:Morris中序周遊+思路二
class Solution {
// 這裡與思路二一緻
Stack<Integer> stack;
int max = 0;
int base = 1;
int count = 0;
public int[] findMode(TreeNode root) {
stack = new Stack<>();
// Morris中序周遊思路若有不懂則傳回上方解題思路章節
TreeNode cur = root; // 前驅節點cur
TreeNode rightend = null; // 左子樹最右的節點rightend
// Morris中序周遊本體
// 在新的周遊方法學會之後,還得知道什麼時候更新max、base、count、stack
// 有一種情況比較好了解:周遊到最左的時候對cur進行更新,這點和普通中序周遊大體類似
// 還有一種情況:rightend的right指針指向cur時,對cur進行更新,也就是傳回前驅節點時進行更新
while(cur != null) {
// 如果cur無左子樹,cur向右移動(cur=cur.right)
if(cur.left == null) {
func(cur);
cur = cur.right;
// 如果cur有左子樹,找到cur左子樹上最右的節點,記為rightend
} else {
rightend = cur.left;
while(rightend.right != null && rightend.right != cur) {
rightend = rightend.right;
}
// 如果rightend的right指針指向空,讓其指向cur,cur向左移動(cur=cur.left)
if(rightend.right == null) {
rightend.right = cur;
cur = cur.left;
// 如果rightend的right指針指向cur,讓其指向空,cur向右移動(cur=cur.right)
} else if (rightend.right == cur) {
func(cur);
rightend.right = null;
cur = cur.right;
}
}
}
// stack裡存儲的都是衆數了
int[] ints = new int[stack.size()];
for(int i = 0; i < ints.length; ++i) {
ints[i] = stack.pop();
}
return ints;
}
// 這個func的作用是更新count+更新base+更新max+更新stack
// 說白了就是把思路二的左右子樹的遞歸給删去了
// 因為主程式的外循環是while(cur != null),是以實參一定不是null,不用考慮null的情況了
public void func(TreeNode node) {
if(node.val == base) {
++count;
} else {
count = 1;
base = node.val;
}
if(count > max) {
max = count;
stack.clear();
stack.push(node.val);
} else if(count == max) {
stack.push(node.val);
}
}
}
注意點
- 個人認為思路二就很可以了,再進階一點可以再額外掌握Morris中序周遊。