501. 二叉搜索树中的众数

题目描述

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

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

假定 BST 满足如下定义：

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

示例 1：

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

示例 2：

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

提示：

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

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

解法一：中序遍历

 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
40
41


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findMode(root *TreeNode) []int {
    // -10^5 <= root.Val <= 10^5
    // base initially is zero
    var base, count, maxCount int
    var ans []int

    update := func(val int) {
        if val == base {
            count++
        } else {
            base, count = val, 1
        }

        if count == maxCount {
            ans = append(ans, base)
        } else if count > maxCount {
            ans = []int{base}
            maxCount = count
        }
    }

    var inorder func(root *TreeNode)
    inorder = func(root *TreeNode) {
        if root == nil {
            return
        }
        inorder(root.Left)
        update(root.Val)
        inorder(root.Right)
    }
    inorder(root)
    return ans
}