501. 二叉搜索树中的众数

一、题目描述

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

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

例如：

给定BST[1, null, 2, 2],

     1
     \
      2
     /
    2

返回[2]。

提示：如果众数超过1个，不需考虑输出顺序

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

二、思路

搜索二叉树进行中序遍历，得到的结果是有序的，所以结果中的相同的数是连续出现的，只需要统计 出现的次数，然后比较找到出现次数最多的一个或多个数保存返回即可。

三、代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        # 当当前节点值与前一个不一样时，对保存的数值与出现的次数进行更新
        def update(cur, sums):
            nonlocal result
            if sums > result[1]:
                result[0] = [cur]
                result[1] = sums
            elif sums == result[1]:
                result[0].append(cur)

        def inOrder(root):
            nonlocal sums, cur
            if root:
                inOrder(root.left)
                if root.val == cur:
                    sums += 1
                else:
                    update(cur, sums)
                    cur = root.val
                    sums = 0
                    sums += 1

                inOrder(root.right)

        # 第一个数组元素负责保存出现的一个或多个出现次数一样的众数；
        # 第二个元素是出现的次数
        result = [[], 0]
        # 统计每个数出现的次数
        sums = 0
        # 当前的数
        cur = ''
        inOrder(root)
        # 特殊情况：最后连续多个数都一样，在递归中没有被统计进去
        update(cur, sums)
        return result[0]

四、表现

运行时间	表现	内存消耗	表现
104ms	8.63%	17.2MB	67.22%