【代码随想录day21】二叉搜索树中的众数

题目

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

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

假定 BST 满足如下定义：

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

思路 

如果不使用额外空间，至少需要用两个指针来判断相邻的两个元素值是否相等，同时设置计数器与最大计数进行比较，在中序遍历（有序序列）过程中不断更新结果。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.maxCount = 0
        self.count = 0
        self.pre = None
        self.res = []

    def solve(self,root):
        if not root:
            return 
        # 中序遍历为有序序列
        self.solve(root.left)
        # 遍历第一个节点，计数1
        if self.pre is None:
            self.count = 1
        # 遇到与之前相等的节点，+1
        elif self.pre.val == root.val:
            self.count += 1
        else:
            self.count = 1
        self.pre = root

        if self.count>self.maxCount:
            self.maxCount = self.count
            self.res = [root.val]
        elif self.count == self.maxCount:
            self.res.append(root.val)
        self.solve(root.right)

    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        self.solve(root)
        return self.res