501. 二叉搜索树中的众数

题目

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

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

假定 BST 满足如下定义：

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

难度：🌟🌟

示例 1：

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

示例 2：

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

提示：

• 树中节点的数目在范围 [1, 10⁴] 内
• -10⁵ <= Node.val <= 10⁵

题解

这题思路是先序遍历，对每个节点值计数，并使用 map 结构把计数保存下来，同时记录下当前出现的频率最高的节点值个数 maxCnt。

1. 如果当前节点值出现次数 大于 maxCnt，则更新 maxCnt，然后清空结果集，重新记录结果；
2. 如果当前节点值出现次数 等于 maxCnt，则将当前节点值添加到结果集中；
3. 如果当前节点值出现次数 小于 maxCnt，忽略。

上述思路能解决此问题，但没有利用到二叉搜索树的结构特性。

代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findMode(root *TreeNode) []int {
	var res []int
	cntMap := make(map[int]int)
	maxCnt := 0
	var preorder func(node *TreeNode)
	preorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		cntMap[node.Val]++
		cnt := cntMap[node.Val]
		if cnt > maxCnt {
			maxCnt = cnt
			// 删除 res 中之前保存的众数
			res = nil
			// 添加到结果中
			res = append(res, node.Val)
		} else if cnt == maxCnt {
			res = append(res, node.Val)
		}
		preorder(node.Left)
		preorder(node.Right)
		return
	}
	preorder(root)
	return res
}