**如果不是二叉搜索树** ```python # 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]: # 统计频率 value_map = defaultdict( int ) def preorder( r ): if not r: return value_map[ r.val ] += 1 preorder( r.left ) preorder( r.right ) preorder( root ) # 按照频率升序排序 value_map_list = list( value_map.items() ) def quicksort( l, r ): if l >= r: return pivot = value_map_list[ ( l + r ) // 2 ][ 1 ] i, j = l - 1, r + 1 while i < j: i += 1 # 找第一个小于 pivot的位置 i停留 while value_map_list[ i ][ 1 ] > pivot: i += 1 j -= 1 # 找第一个大于 pivot的位置 j停留 while value_map_list[ j ][ 1 ] < pivot: j -= 1 if i < j: value_map_list[ i ], value_map_list[ j ] = value_map_list[ j ], value_map_list[ i ] quicksort( l, j ) quicksort( j + 1, r ) quicksort( 0, len( value_map_list ) - 1 ) ans = [ value_map_list[ 0 ][ 0 ] ] for i in range( 1, len( value_map_list ) ): # 第一个位置是出现最多的 和第一个出现次数一致的加入结果集 if value_map_list[ i ][ 1 ] != value_map_list[ 0 ][ 1 ]: break ans.append( value_map_list[ i ][ 0 ] ) return ans ``` **对于二叉搜索树有更加巧妙的方式** 由于二叉搜索树的中序遍历是有序的，所以： - 设置pre和cur记录前一个节点和当前节点，从而计算count - 设置max_count来统计过程中出现的最大的频率，最大频率发生变化时，清空结果集，加入新的元素 ```python # 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]: ans = [] if not root: return ans self.pre = None self.cur = root self.count = 0 self.max_count = 0 def inorder( r ): if not r: return inorder( r.left ) # self.cur可以完全用r代替 self.cur = r if not self.pre: # 第一个节点 self.count = 1 elif self.cur.val == self.pre.val: # 节点元素相同 self.count += 1 else: # 节点元素不同 重置 self.count = 1 self.pre = self.cur # 检验max_count print( self.count, self.max_count ) if self.count > self.max_count: # 最大频次发生变化 清空结果集 加入最新的 ans.clear() self.max_count = self.count # 加入结果集 if self.count == self.max_count: ans.append( self.cur.val ) inorder( r.right ) inorder( root ) return ans ```