服装手机商城网站建设,淄博网站制作服务优化,直通车怎么开,网站备案基础知识题目 给你一个含重复值的二叉搜索树#xff08;BST#xff09;的根节点 root #xff0c;找出并返回 BST 中的所有 众数#xff08;即#xff0c;出现频率最高的元素#xff09;。
如果树中有不止一个众数#xff0c;可以按 任意顺序 返回。
假定 BST 满足如下定义BST的根节点 root 找出并返回 BST 中的所有 众数即出现频率最高的元素。
如果树中有不止一个众数可以按 任意顺序 返回。
假定 BST 满足如下定义
结点左子树中所含节点的值 小于等于 当前节点的值 结点右子树中所含节点的值 大于等于 当前节点的值 左子树和右子树都是二叉搜索树 思路 如果不使用额外空间至少需要用两个指针来判断相邻的两个元素值是否相等同时设置计数器与最大计数进行比较在中序遍历有序序列过程中不断更新结果。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def __init__(self):self.maxCount 0self.count 0self.pre Noneself.res []def solve(self,root):if not root:return # 中序遍历为有序序列self.solve(root.left)# 遍历第一个节点计数1if self.pre is None:self.count 1# 遇到与之前相等的节点1elif self.pre.val root.val:self.count 1else:self.count 1self.pre rootif self.countself.maxCount:self.maxCount self.countself.res [root.val]elif self.count self.maxCount:self.res.append(root.val)self.solve(root.right)def findMode(self, root: Optional[TreeNode]) - List[int]:self.solve(root)return self.res
