题目
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。如果树中有不止一个众数，可以按任意顺序返回。
假定 BST 满足如下定义：结点左子树中所含节点的值小于等于当前节点的值，结点右子树中所含节点的值大于等于当前节点的值，左子树和右子树都是二叉搜索树
例：
输入：root = [1,null,2,2]
输出：[2]
方法：递归
根据二叉搜索树的特性我们可知，以中序遍历的方式可以得到该树由小到大的元素值，所以只有临近的节点值可能相同
__ init __ 部分：定义
- pre 表示上一个节点
- count 表示此时节点值的出现次数
- max_count 表示节点值的最大出现次数
- result 所有节点出现次数等于最大出现次数的节点值
findMode 部分：
- 判断是否为空树
- 开始进行记录和查找出现次数最多的节点值
- 返回所有出现频率最高的元素的值
search 部分：
- 判断是否为空节点
- 调用 search 函数，对左子树进行遍历
- 若节点为第一个节点，即不存在上一个节点，那么该节点值的出现次数一定为一；若节点值等于上一个节点值，那么该节点值的出现次数加一；若节点值不等于上一个节点值，那么该节点的出现次数一定为一
- 因为节点可以通过函数的参数传递，但是上一个节点并不可以，所以为了后续的遍历需要手动将此时节点变成上一个节点
- 若节点的出现次数等于最大出现次数，那么该节点值可以移入 result 列表中；若节点的出现次数大于最大出现次数，那么 result 列表清空，同时将该节点值移入 result 列表中
- 调用 search 函数，对右子树进行遍历
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def __init__(self):
self.pre = TreeNode()
self.count = 0
self.max_count = 0
self.result = []
def findMode(self, root):
if not root:
return None
self.search(root)
return self.result
def search(self, node):
if not node:
return None
self.search(node.left)
if not self.pre:
self.count = 1
elif self.pre.val == node.val:
self.count += 1
else:
self.count = 1
self.pre = node
if self.count == self.max_count:
self.result.append(node.val)
if self.count> self.max_count:
self.max_count = self.count
self.result = [node.val]
self.search(node.right)
