LeetCode-501. 二叉搜索树中的众数
2020-09-242020-09-25
问题地址
LeetCode501. 二叉搜索树中的众数
问题描述
规则
- 给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
- 假定 BST 有如下定义：
- 结点左子树中所含结点的值小于等于当前结点的值
- 结点右子树中所含结点的值大于等于当前结点的值
- 左子树和右子树都是二叉搜索树
示例
- 示例一：
给定 BST [1,null,2,2],
1
\
2
/
2
返回[2].
提示：
- 如果众数超过1个，不需考虑输出顺序
进阶
- 你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
解析
解题思路
- 这个题目最直观的做法是遍历的时候使用Map统计数字出现次数，然后根据Map的统计结果找出答案。
- 但是这种做法的缺点就是没有利用：这里的输入是BST。
数据操作分析
复杂度分析
- 时间复杂度
- 空间复杂度
编码实现
public class LeetCode0501_FindModeInBinarySearchTree {
public int[] findMode(TreeNode root) {
Map<Integer, Integer> map = new HashMap<>();
findMode(root, map);
List<Integer> resList = new ArrayList<Integer>();
Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Integer, Integer> next = iterator.next();
if (resList.isEmpty()) {
resList.add(next.getKey());
} else {
if (next.getValue() > map.get(resList.get(0))) {
resList.remove(0);
resList.removeAll(resList);
resList.add(next.getKey());
} else if (next.getValue() == map.get(resList.get(resList.size() - 1))) {
resList.add(next.getKey());
}
}
}
int[] res = new int[resList.size()];
for (int i = 0; i < resList.size(); i++) {
res[i] = resList.get(i);
}
return res;
}
private void findMode(TreeNode root, Map<Integer, Integer> map) {
if (root == null) return;
int key = root.val;
int value = 0;
if (map.containsKey(key)) {
value = map.get(key) + 1;
} else {
value++;
}
map.put(key, value);
findMode(root.left, map);
findMode(root.right, map);
}
}
优化思路
- 由于输入为BST，使用中序遍历可以得到一个非递减的序列，此时题目将变为给出一个有序数组，找出出现次数最多的元素。
- 如果是数组，从头遍历比较相邻的元素即可，树应该怎么做呢？
- 定义一个变量 preNode 指向前一个节点，使用 curNode 与 preNode比较。
- 如何只遍历一遍就找出出现次数最多的集合？
- 我们可以定义两个变量分别记录出现最多的次数maxCount，当前数字的出现次数count；
- 如果count=maxCount， 则将当前元素加入到结果集中；
- 如果count>maxCount， 此时我们需要更新清空结果集，将当前元素放入结果集并且使maxCount=count；
数据操作分析
复杂度分析
- 时间复杂度
- 空间复杂度
编码实现
public class LeetCode0501_FindModeInBinarySearchTree_1 {
List<Integer> list = new ArrayList<Integer>();
int maxCount = 0;//最大出现次数
int count = 0;//当前元素出现次数
TreeNode pre = null;//前驱节点
public int[] findMode(TreeNode root) {
addTreeValue(root);
if (list.isEmpty()) return new int[0];
int[] ans = new int[list.size()];
for (int i = 0; i < ans.length; i++) {
ans[i]=list.get(i);
}
return ans;
}
private void addTreeValue(TreeNode root) {
if (root == null) return;
addTreeValue(root.left);//移动到最左叶子
if (pre == null) {//pre为空，说明是第一个元素
count = 1;
} else if (root.val == pre.val) {//判断相邻元素是否相同
count++;
} else {
count = 1;//与前一个数值不同，当前元素统计值归1
}
pre = root;//向前移动
if (count == maxCount) {//当前元素出现次数等于最大出现次数
list.add(root.val);
}
if (count > maxCount) {//当前元素出现次数大于最大出现次数，需要清空结果集
list.clear();
maxCount = count;
list.add(root.val);
}
addTreeValue(root.right);
}
}
官方解法
方法一：Morris 中序遍历
思路：
- 首先我们一定能想到一个最朴素的做法：因为这棵树的中序遍历是一个有序的序列，所以我们可以先获得这棵树的中序遍历，然后从扫描这个中序遍历序列，然后用一个哈希表来统计每个数字出现的个数，这样就可以找到出现次数最多的数字。但是这样做的空间复杂度显然不是 O(1) 的，原因是哈希表和保存中序遍历序列的空间代价都是 O(n)。
- 首先，我们考虑在寻找出现次数最多的数时，不使用哈希表。 这个优化是基于 BST 中序遍历的性质：一棵 BST 的中序遍历序列是一个非递减的有序序列。例如：
1
/ \
0 2
/ \ /
-1 0 2
- 这样一颗 BST 的中序遍历序列是 { -1, 0, 0, 1, 2, 2 }。我们可以发现重复出现的数字一定是一个连续出现的，例如这里的 0 和 2，它们都重复出现了，并且所有的 0 都集中在一个连续的段内，所有的 2 也集中在一个连续的段内。我们可以顺序扫描中序遍历序列，用 \rm base 记录当前的数字，用 \rm count 记录当前数字重复的次数，用 \rm maxCount 来维护已经扫描过的数当中出现最多的那个数字的出现次数，用 \rm answer 数组记录出现的众数。每次扫描到一个新的元素：
- 首先更新 \rm base 和 \rm count:
- 如果该元素和 \rm base 相等，那么 \rm count 自增 11
- 否则将 \rm base 更新为当前数字，\rm count 复位为 11
- 然后更新 \rm maxCount：
- 如果 \rm count = maxCount，那么说明当前的这个数字（\rm base）出现的次数等于当前众数出现的次数，将 \rm base 加入 \rm answer 数组
- 如果 \rm count>maxCount，那么说明当前的这个数字（\rm base）出现的次数大于当前众数出现的次数，因此，我们需要将 \rm maxCount 更新为 \rm count，清空 \rm answer 数组后将 \rm base 加入 \rm answer 数组
- 首先更新 \rm base 和 \rm count:
- 我们可以把这个过程写成一个 \rm update 函数。这样我们在寻找出现次数最多的数字的时候就可以省去一个哈希表带来的空间消耗。
- 然后，我们用 Morris 中序遍历的方法把中序遍历的空间复杂度优化到 O(1)。 我们在中序遍历的时候，一定先遍历左子树，然后遍历当前节点，最后遍历右子树。在常规方法中，我们用递归回溯或者是栈来保证遍历完左子树可以再回到当前节点，但这需要我们付出额外的空间代价。我们需要用一种巧妙地方法可以在 O(1) 的空间下，遍历完左子树可以再回到当前节点。我们希望当前的节点在遍历完当前点的前驱之后被遍历，我们可以考虑修改它的前驱节点的 \rm right 指针。当前节点的前驱节点的 \rm right 指针可能本来就指向当前节点（前驱是当前节点的父节点），也可能是当前节点左子树最右下的节点。如果是后者，我们希望遍历完这个前驱节点之后再回到当前节点，可以将它的 \rm right 指针指向当前节点。
- Morris 中序遍历的一个重要步骤就是寻找当前节点的前驱节点，并且 Morris 中序遍历寻找下一个点始终是通过转移到 \rm right 指针指向的位置来完成的。
- 如果当前节点没有左子树，则遍历这个点，然后跳转到当前节点的右子树。
- 如果当前节点有左子树，那么它的前驱节点一定在左子树上，我们可以在左子树上一直向右行走，找到当前点的前驱节点。
- 如果前驱节点没有右子树，就将前驱节点的 \rm right 指针指向当前节点。这一步是为了在遍历完前驱节点后能找到前驱节点的后继，也就是当前节点。
- 如果前驱节点的右子树为当前节点，说明前驱节点已经被遍历过并被修改了 \rm right 指针，这个时候我们重新将前驱的右孩子设置为空，遍历当前的点，然后跳转到当前节点的右子树。
- 因此我们可以得到这样的代码框架：
TreeNode *cur = root, *pre = nullptr;
while (cur) {
if (!cur->left) {
// ...遍历 cur
cur = cur->right;
continue;
}
pre = cur->left;
while (pre->right && pre->right != cur) {
pre = pre->right;
}
if (!pre->right) {
pre->right = cur;
cur = cur->left;
} else {
pre->right = nullptr;
// ...遍历 cur
cur = cur->right;
}
}
- 最后我们将 …遍历 cur 替换成之前的 \rm update 函数即可。
复杂度分析：
-
时间复杂度:O(n)。每个点被访问的次数不会超过两次，故这里的时间复杂度是 O(n)。
-
空间复杂度：O(1)。使用临时空间的大小和输入规模无关。
编码实现
class Solution {
int base, count, maxCount;
List<Integer> answer = new ArrayList<Integer>();
public int[] findMode(TreeNode root) {
TreeNode cur = root, pre = null;
while (cur != null) {
if (cur.left == null) {
update(cur.val);
cur = cur.right;
continue;
}
pre = cur.left;
while (pre.right != null && pre.right != cur) {
pre = pre.right;
}
if (pre.right == null) {
pre.right = cur;
cur = cur.left;
} else {
pre.right = null;
update(cur.val);
cur = cur.right;
}
}
int[] mode = new int[answer.size()];
for (int i = 0; i < answer.size(); ++i) {
mode[i] = answer.get(i);
}
return mode;
}
public void update(int x) {
if (x == base) {
++count;
} else {
count = 1;
base = x;
}
if (count == maxCount) {
answer.add(base);
}
if (count > maxCount) {
maxCount = count;
answer.clear();
answer.add(base);
}
}
}