501. 二叉搜索树中的众数

🟢 🔖 树 深度优先搜索 二叉搜索树 二叉树 🔗 力扣open in new window LeetCodeopen in new window

题目

Given the root of a binary search tree (BST) with duplicates, return _all themode(s)open in new window (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.

Example 1:

Input: root = [1,null,2,2]
Output: [2]

Example 2:

Input: root = [0]
Output: [0]

Constraints:

The number of nodes in the tree is in the range [1, 104].
-10^5 <= Node.val <= 10^5

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

题目大意

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

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

假定 BST 满足如下定义：

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

示例 1：

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

示例 2：

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

提示：

树中节点的数目在范围 [1, 104] 内
-10^5 <= Node.val <= 10^5

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

解题思路

题目要求找到二叉搜索树（BST）的众数（即出现频率最高的元素），由于 BST 的中序遍历结果是一个升序排列的数组，因此相同值的节点会连续出现在遍历结果中，可以通过中序遍历逐一访问节点，同时记录出现频率来解决问题。

初始化变量：
- maxFreq = 0：记录所有值中最高的出现频率。
- curVal = 0：记录当前正在处理的值。
- curFreq = 0：记录当前值的出现频率。
- res = []：存储所有频率等于 maxFreq 的值。
中序遍历：
- 树为空时，直接返回空数组。
- 递归遍历左子树。
- 处理当前节点：
  - 如果当前值与 curVal 相同，增加 curFreq。
  - 如果不同，更新 curVal 并重置 curFreq 为 1。
  - 更新 maxFreq，根据频率决定是否更新 res。
- 递归遍历右子树。
返回结果：
- 返回存储众数的数组 res。

复杂度分析

时间复杂度：O(n)，其中 n 是节点数，中序遍历整棵树一次。
空间复杂度：O(h + m)
- 递归调用栈的空间复杂度为 O(h)，其中 h 是树的高度。
- 结果数组 res 的空间复杂度为 O(m)，其中 m 是众数的数量。
- 请注意，如果我们不计算递归调用堆栈空间和结果数组使用的空间（如问题描述的后续内容中所述），则此方法使用 O(1) 空间，因为我们仅使用几个额外的变量，如 maxFreq, curFreq, curVal。

代码

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var findMode = function (root) {
	let maxFreq = 0; // 当前最大频率
	let curFreq = 0; // 当前值的频率
	let curVal = 0; // 当前处理的值
	let res = []; // 存储众数的结果数组

	// 中序遍历函数
	const dfs = (node) => {
		if (!node) return; // 如果节点为空，直接返回

		dfs(node.left); // 遍历左子树

		// 处理当前节点
		if (node.val === curVal) {
			curFreq += 1; // 当前值与之前相同，频率增加
		} else {
			curFreq = 1; // 当前值不同，重置频率为 1
			curVal = node.val; // 更新当前值
		}

		// 更新最大频率和结果数组
		if (curFreq > maxFreq) {
			maxFreq = curFreq; // 更新最大频率
			res = [node.val]; // 重新记录结果
		} else if (curFreq === maxFreq) {
			res.push(node.val); // 如果频率相等，加入结果
		}

		dfs(node.right); // 遍历右子树
	};

	dfs(root); // 开始中序遍历
	return res; // 返回结果
};

501. 二叉搜索树中的众数

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

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

501. 二叉搜索树中的众数

题目

题目大意

解题思路

复杂度分析

代码

相关题目