LC 501.二叉搜索树中的众数

501.二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

• 结点左子树中所含节点的值 小于等于 当前节点的值
• 结点右子树中所含节点的值 大于等于 当前节点的值
• 左子树和右子树都是二叉搜索树

示例 1：

输入： root = [1,null,2,2]
输出：[2]

示例 2：

输入： root = [0]
输出：[0]

提示：

• 树中节点的数目在范围 $[1,10^4]$ 内
• $-10^5\le Node.val\le 10^5$

进阶： 你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

解法一(递归 + 中序遍历)

思路分析：

1. 首先题目给出二叉搜索树的定义，因此可以使用中序遍历来遍历二叉树，从而得到一个有序的序列，然后根据该有序的序列寻找众数。
2. 使用递归的方式来实现二叉搜索树的中序遍历
3. 同时对于递归的返回值，为null，递归的参数则有二叉树的节点
4. 对于递归的边界条件，若二叉树的节点为null，结束递归
5. 对于递归的一般过程；则对该节点的值进行统计与判断
   1. 首先需要一个全局变量val来记录上一个节点的值，初始为root.val，然后使用一个全局变量num来统计对应val值出现的次数，初始为0
   2. 当遍历到某节点时，若该节点的值node.val == val，则++ num
   3. 若该节点的值不等于val，则将已经统计记录的val和num进行判断，另一个全局变量maxNum用于记录出现某值的最大次数
      1. 若num > maxNum，则出现新的众数，重新记录保存val
      2. 若num == maxNum，则将该众数继续保存到已有的记录中
      3. 若num < maxNum，则无需操作
   4. 当判断记录结束后，更新val和num

实现代码如下：

class Solution {
	int val;	// 用于记录中序遍历上一个节点的值
	int num;	// 用于记录值等于val的节点个数
	int maxNum;	// 用于记录num出现的最大值
	List<Integer> ans;	// 用于保存记录出现的众数
    public int[] findMode(TreeNode root) {
		val = root.val;	// 初始化为根节点
		ans = new LinkedList<>();
		doFindMode(root);
		updateAns();	// 再进行更新ans 防止漏掉序列最后连续的数值
		int[] arr = new int[ans.size()];
		for (int i = 0; i < ans.size(); ++ i) {
			arr[i] = ans.get(i);
		}
		return arr;
    }
	private void doFindMode(TreeNode node) {
		if (node == null)
			return ;
		doFindMode(node.left);		// 遍历左子树
		if (node.val == val) {
			++ num;
		} else {
			updateAns();	// 对列表进行更新
			val = node.val;
			num = 1;
		}
		doFindMode(node.right);		// 遍历右子树
	}
	private void updateAns() {
		if (num > maxNum) {
			ans.clear();	// 清除记录
			ans.add(val);	// 记录新的众数
			maxNum = num;	// 更新最大num
		} else if (num == maxNum) {
			ans.add(val);	// 增加新的众数
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

提交结果如下：

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:43.9 MB,击败了28.46% 的Java用户

复杂度分析：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$