二叉搜索树中的众数
难度:
标签:
题目描述
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2] 输出：[2]
示例 2：
输入：root = [0] 输出：[0]
提示：
- 树中节点的数目在范围
[1, 104]内 -105 <= Node.val <= 105
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
代码结果
运行时间: 56 ms, 内存: 19.1 MB
/*
* 题目思路：
* 1. 使用Java Stream实现，我们可以先进行中序遍历收集所有元素，然后使用Collectors.groupingBy统计频率。
* 2. 通过Collectors.maxBy找到最大频率，然后筛选出所有具有最大频率的元素。
*/
import java.util.*;
import java.util.stream.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class SolutionStream {
public int[] findMode(TreeNode root) {
List<Integer> values = new ArrayList<>();
inOrder(root, values);
Map<Integer, Long> frequencyMap = values.stream()
.collect(Collectors.groupingBy(x -> x, Collectors.counting()));
long maxFrequency = frequencyMap.values().stream()
.max(Long::compare).orElse(0L);
return frequencyMap.entrySet().stream()
.filter(entry -> entry.getValue() == maxFrequency)
.mapToInt(Map.Entry::getKey)
.toArray();
}
private void inOrder(TreeNode node, List<Integer> values) {
if (node == null) return;
inOrder(node.left, values);
values.add(node.val);
inOrder(node.right, values);
}
}
解释
方法:
这个题解使用中序遍历的方式遍历二叉搜索树，同时使用一些变量来记录当前节点的值、出现次数、最大出现次数等信息。在遍历过程中，通过比较当前节点值与上一个节点值是否相同，来判断当前节点是否为众数。如果当前节点出现次数等于最大出现次数，将当前节点值加入结果列表；如果大于最大出现次数，则更新结果列表为只包含当前节点值，并更新最大出现次数。遍历完整棵树后，结果列表中就是所有的众数。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么选择中序遍历来处理这个问题，而不是前序或后序遍历？
▷🦆
在算法中，如何确保在更新最大出现次数`maxTimes`时，能正确地从结果列表`res`中移除旧的众数？
▷🦆
当树中只有一个节点时，算法的表现是怎样的？是否直接返回该单个节点作为众数，还是需要遍历整棵树？
▷🦆
题解中提到使用栈来模拟递归调用，这种方法与直接使用系统调用栈的递归相比，有什么优势或劣势？
▷
