501. 二叉搜索树中的众数

描述

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

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],

   1
    \
     2
    /
   2

返回[2].

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

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

力扣（LeetCode）

暴力解

1. 遍历 + 统计

class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        c = collections.defaultdict(int)
        if not root: return []
        def f(root):
            if root:
                c[root.val] += 1
                f(root.left)
                f(root.right)
        f(root)        
        m = max(c.values())
        return [k for k, v in c.items() if v == m]

O(1) 空间解

1. 上面的解法没有用到二叉树的性质。利用中序遍历，得到的序列是有序的。 也就是说我们在遍历的过程中， 都是先看到小的元素，然后在变大。对于一个排好序的数列， 我们可以用一个临时变量来维护众数的频数。

class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        if not root: return []
        ret,pre,mf, fre  = [], 0, 0, 0
        def inorder(root):
            nonlocal pre, fre, mf, ret
            if not root: 
                if fre > mf:
                    ret = [pre]
                elif fre == mf and (not ret or ret[-1] != pre):    
                    ret.append(pre)
                return
            inorder(root.left)
            if root.val == pre: 
                fre += 1
            else:    
                if fre == mf and (not ret or ret[-1] != pre):
                    ret.append(pre)
                elif fre > mf:    
                    ret, mf = [pre], fre
                pre, fre = root.val, 1
            inorder(root.right)
        inorder(root)    
        return ret