題目描述
給定一個(gè)有相同值的二叉搜索樹(shù)（BST）典徊，找出 BST 中的所有眾數(shù)（出現(xiàn)頻率最高的元素）。
假定 BST 有如下定義：
- 結(jié)點(diǎn)左子樹(shù)中所含結(jié)點(diǎn)的值小于等于當(dāng)前結(jié)點(diǎn)的值
- 結(jié)點(diǎn)右子樹(shù)中所含結(jié)點(diǎn)的值大于等于當(dāng)前結(jié)點(diǎn)的值
- 左子樹(shù)和右子樹(shù)都是二叉搜索樹(shù)
示例 1:
輸入:
給定 BST [1,null,2,2]
1
\
2
/
2
返回[2].
解法1
利用二叉搜索樹(shù)特性
因?yàn)槎嫠阉鳂?shù)的中序遍歷為有序列表略水，所以相當(dāng)于在有序列表中，取眾數(shù)的值。所以只需要一次遍歷即可獲得每個(gè)元素的出現(xiàn)次數(shù)托启，即可獲得眾數(shù)。
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
作為普通二叉樹(shù)處理
遍歷二叉樹(shù)攘宙，將出現(xiàn)次數(shù)保存在map對(duì)象中屯耸，若次數(shù)等于最大出現(xiàn)次數(shù)，則添加元素到ret結(jié)果集中蹭劈；若高于最大出現(xiàn)次數(shù)疗绣，則更新最大次數(shù)并清除結(jié)果集，重新添加當(dāng)前元素铺韧。
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)
