LeetCode 0501.二叉搜索树中的众数

二叉搜索树中的众数

LeetCode501. 二叉搜索树中的众数

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

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

假定 BST 满足如下定义：

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

思路

如果不是二叉搜索树，最直观的方法一定是把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合

既然是搜索树，它中序遍历就是有序的

中序遍历输出：1 2 3 4 5 6

当频率count大于maxCount的时候，把这个元素加入到结果集中，不仅要更新maxCount，而且要清空结果集，因为结果集之前的元素都失效了。

代码

Go

 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


// 查找BST中的众数
func findMode(root *TreeNode) []int {
    res := make([]int, 0)           // 结果集
    count := 1                      // 计数器
    max := 1                        // 最大频率
    var prev *TreeNode              // 指向前一个元素
    var travel func(node *TreeNode) // 声明匿名变量
    travel = func(node *TreeNode) { // 实现匿名函数
        if node == nil {
            return
        }
        travel(node.Left) // 递归 左
        if prev != nil && prev.Val == node.Val {
            count++ // 重复出现 计数器+1
        } else {
            count = 1 // 没重复出现 计数器置1
        }
        if count >= max { // 达到或超过最大频率
            if count > max && len(res) > 0 {
                res = []int{node.Val} // 超过最大频率 清空结果集 只把这个元素加入到结果集中
            } else {
                res = append(res, node.Val) // 达到最大频率 把这个元素加入到结果集中即可
            }
            max = count // 更新最大频率
        }
        prev = node        // prev指向该节点
        travel(node.Right) // 递归 右
    }
    travel(root) // 调用匿名函数
    return res
}

Link

GitHub