难度: Easy
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
示例 1：
输入：root = [1,null,2,2] 输出：[2]
示例 2：
输入：root = [0] 输出：[0]
提示：
[1, 104] 内-105 <= Node.val <= 105进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
运行时间: 56 ms
内存: 19.1 MB
# 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 findMode(self, root: Optional[TreeNode]) -> List[int]:
lastVal = 0
curTimes = 0
maxTimes = 0
stack = []
res = []
while root is not None or len(stack) > 0:
if root is not None:
stack.append(root)
root = root.left
else:
root = stack.pop()
if root.val == lastVal:
curTimes += 1
else:
curTimes = 1
lastVal = root.val
if curTimes == maxTimes:
res.append(root.val)
elif curTimes > maxTimes:
res = [root.val]
maxTimes = curTimes
root = root.right
return res
这个题解使用中序遍历的方式遍历二叉搜索树，同时使用一些变量来记录当前节点的值、出现次数、最大出现次数等信息。在遍历过程中，通过比较当前节点值与上一个节点值是否相同，来判断当前节点是否为众数。如果当前节点出现次数等于最大出现次数，将当前节点值加入结果列表；如果大于最大出现次数，则更新结果列表为只包含当前节点值，并更新最大出现次数。遍历完整棵树后，结果列表中就是所有的众数。
时间复杂度: O(n)
空间复杂度: O(n)
# 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 findMode(self, root: Optional[TreeNode]) -> List[int]:
lastVal = 0 # 记录上一个节点的值
curTimes = 0 # 记录当前值出现的次数
maxTimes = 0 # 记录最大出现次数
stack = [] # 模拟递归调用的栈
res = [] # 记录结果（所有的众数）
while root is not None or len(stack) > 0:
if root is not None:
stack.append(root) # 当前节点不为空，入栈
root = root.left # 移动到左子节点
else:
root = stack.pop() # 当前节点为空，出栈
if root.val == lastVal: # 如果当前节点值与上一个节点值相同
curTimes += 1 # 当前值出现次数加1
else:
curTimes = 1 # 否则，重置当前值出现次数为1
lastVal = root.val # 更新上一个节点的值
if curTimes == maxTimes: # 如果当前值出现次数等于最大出现次数
res.append(root.val) # 将当前值加入结果列表
elif curTimes > maxTimes: # 如果当前值出现次数大于最大出现次数
res = [root.val] # 更新结果列表，只保存当前值
maxTimes = curTimes # 更新最大出现次数
root = root.right # 移动到右子节点
return res # 返回所有的众数
中序遍历是因为二叉搜索树的特性，中序遍历可以按照递增的顺序访问所有节点。这样在遍历时能够方便比较当前节点的值与前一个访问的节点的值，进而统计每个值出现的次数。如果使用前序或后序遍历，节点的访问顺序将不再保证递增，这将增加统计众数的复杂度，因为需要额外的数据结构来跟踪和比较每个值的出现频率。
在算法中，每当发现当前节点值的出现次数`curTimes`超过了之前的最大出现次数`maxTimes`时，算法会更新`maxTimes`为新的最高出现次数，并且将结果列表`res`设置为只包含当前节点的值。这是通过将`res`赋值为一个只包含当前节点值的新列表来实现的，从而自动移除了之前的众数。
当树中只有一个节点时，算法仍然会遍历这个节点。在这种情况下，由于只有一个节点，它自然成为出现次数最多的节点。算法会在访问这个节点时将其添加到结果列表`res`中，并将`maxTimes`更新为1。因此，算法将返回包含这个单一节点的列表作为众数。即使树只有一个节点，中序遍历仍然会正常执行这个过程。
使用栈来模拟递归调用的优势在于对递归过程的控制更为直观和灵活，特别是在需要进行细致操作的情况下，如迭代中的状态管理和变量更新。此外，这种方法避免了递归可能导致的栈溢出问题，尤其是在处理非常深的树时。然而，这种方法的劣势是代码可能更复杂，难于理解和维护，同时手动管理栈可能比自然的递归调用效率略低。