【代码随想录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 = 0self.count = 0self.pre = Noneself.res = []def solve(self,root):if not root:return # 中序遍历为有序序列self.solve(root.left)# 遍历第一个节点，计数1if self.pre is None:self.count = 1# 遇到与之前相等的节点，+1elif self.pre.val == root.val:self.count += 1else:self.count = 1self.pre = rootif self.count>self.maxCount:self.maxCount = self.countself.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