当前位置：首页 > article >正文

【代码随想录】刷题记录(61)-二叉搜索树中的众数

article 2024/12/24 1:20:52

题目描述：

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

提示：

树中节点的数目在范围 [1, 104] 内
-105 <= Node.val <= 105

我的作答：

二叉树也逐渐模版化了，整体思路和【代码随想录】刷题记录(60)-二叉搜索树的最小绝对差一样，其实根据二叉树的特性，众数只会出现在相邻的元素中，一旦发现这一个结点和下一个结点的值不同，这个结点的值就不会再出现了；

# 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 = None
        self.count = 0
        self.countMax = 0
        self.res = []

    def findMode(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        if not root:
            return None
        self.findMode(root.left) #左
        if not self.pre: #中
            self.count = 1
        elif self.pre.val==root.val:
            self.count += 1
        else:
            self.count = 1
        self.pre = root
        if self.count==self.countMax:
            self.res.append(root.val) #相同次数的众数
        elif self.count>self.countMax:
            self.res = [] #清空原数组
            self.countMax = self.count
            self.res.append(root.val)
        self.findMode(root.right) #右
        return self.res

参考代码：迭代法（看了很多次，没动手写过一次。。）

# 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:
    def findMode(self, root):
        st = []
        cur = root
        pre = None
        maxCount = 0  # 最大频率
        count = 0  # 统计频率
        result = []

        while cur is not None or st:
            if cur is not None:  # 指针来访问节点，访问到最底层
                st.append(cur)  # 将访问的节点放进栈
                cur = cur.left  # 左
            else:
                cur = st.pop()
                if pre is None:  # 第一个节点
                    count = 1
                elif pre.val == cur.val:  # 与前一个节点数值相同
                    count += 1
                else:  # 与前一个节点数值不同
                    count = 1

                if count == maxCount:  # 如果和最大值相同，放进result中
                    result.append(cur.val)

                if count > maxCount:  # 如果计数大于最大值频率
                    maxCount = count  # 更新最大频率
                    result = [cur.val]  # 很关键的一步，不要忘记清空result，之前result里的元素都失效了

                pre = cur
                cur = cur.right  # 右

        return result