[Python手撕]二叉搜索树中的众数

THINK TWICE, CODE ONCE. / 2024-10-21 / 原文

给你一个含重复值的二叉搜索树（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 findMode(self, root: Optional[TreeNode]) -> List[int]:

        def inorder(root):
            if root:
                inorder(root.left)
                
                if root.val == self.cur_val:
                    self.cur_count += 1
                else:
                    self.cur_val = root.val
                    self.cur_count = 1
                
                if self.cur_count == self.count:
                    self.res.append(self.cur_val)
                elif self.cur_count > self.count:
                    self.count = self.cur_count
                    self.res = [self.cur_val]

                inorder(root.right)

        self.cur_val = root.val
        self.cur_count = 0

        self.count = 0
        self.res = []

        inorder(root)

        return self.res