LeetCode刷题实战501：二叉搜索树中的众数
共 2185字，需浏览 5分钟
·
2022-01-23 13:32
Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.
If the tree has more than one mode, return them in any order.
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than or equal to the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
Both the left and right subtrees must also be binary search trees.
示例
解题
class Solution {
// 记录前一个指针
private TreeNode pre = null;
// 计算出现次数
private int count = 0;
// 最大的出现频率
private int maxCount = 0;
private Listlist = new ArrayList<>();
public int[] findMode(TreeNode root) {
searchBST(root);
int[] ans = new int[list.size()];
for (int i = 0; i < ans.length; i++) {
ans[i] = list.get(i);
}
return ans;
}
private void searchBST(TreeNode cur) {
if (cur == null) return;
searchBST(cur.left);
if (pre == null) {
count = 1;
} else if (pre.val == cur.val) {
count++;
} else if (pre.val != cur.val) {
count = 1;
}
pre = cur;
if (count == maxCount) {
list.add(cur.val);
}
if (count > maxCount) {
maxCount = count;// 更新最大的频率
list.clear(); // 清空列表，之前的元素失效
list.add(cur.val);
}
searchBST(cur.right);
}
}