题目描述
给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。
假定 BST 有如下定义:
示例 1:
输入: 给定 BST [1,null,2,2]
1
\
2
/
2
返回[2].
解法1
利用二叉搜索树特性
因为二叉搜索树的中序遍历为有序列表,所以相当于在有序列表中,取众数的值。所以只需要一次遍历即可获得每个元素的出现次数,即可获得众数。
class Solution(object):
def findMode(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
self.maxTimes,self.curTimes=1,0
self.ret,self.lastNode=[],None
def addToRet(node):
if node:
addToRet(node.left)
if self.lastNode and self.lastNode.val==node.val:
self.curTimes+=1
else:
self.curTimes=1
self.lastNode=node
if self.curTimes==self.maxTimes:
self.ret.append(node.val)
elif self.curTimes>self.maxTimes:
self.ret,self.maxTimes=[],self.curTimes
self.ret.append(node.val)
addToRet(node.right)
addToRet(root)
return self.ret
解法2
作为普通二叉树处理
遍历二叉树,将出现次数保存在map
对象中,若次数等于最大出现次数,则添加元素到ret
结果集中;若高于最大出现次数,则更新最大次数并清除结果集,重新添加当前元素。
class Solution(object):
def findMode(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
self.maxTimes=1
self.map,self.ret=dict(),set()
def addToRet(node):
if node:
addToRet(node.left)
num=self.map.get(node.val,0)+1
self.map[node.val]=num
if num==self.maxTimes:
self.ret.add(node.val)
elif num>self.maxTimes:
self.ret.clear()
self.ret.add(node.val)
self.maxTimes=num
addToRet(node.right)
addToRet(root)
return list(self.ret)