给你一个含重复值的二叉搜索树(BST)的根节点 root
,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。
如果树中有不止一个众数,可以按 任意顺序 返回。
假定 BST 满足如下定义:
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1:
![](https://github.xin/wp-content/uploads/2023/07/80ad66a00f8f91c.jpg)
输入:root = [1,null,2,2] 输出:[2]
示例 2:
输入:root = [0] 输出:[0]
提示:
- 树中节点的数目在范围
[1, 104]
内 -105 <= Node.val <= 105
进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)
题解:
计数法(中序遍历):
func findMode(root *TreeNode) []int {
var result []int
var prev *TreeNode
count := 1
maxCount := 1
var travel func(node *TreeNode)
travel = func(node *TreeNode) {
if node == nil {
return
}
travel(node.Left)
if prev != nil && node.Val == prev.Val {
count++
} else {
count = 1
}
if count >= maxCount {
if count > maxCount && len(result) > 0 {
result = []int{node.Val}
} else {
result = append(result, node.Val)
}
maxCount = count
}
prev = node
travel(node.Right)
}
travel(root)
return result
}
评论前必须登录!
注册