Leetcode 501. 二叉搜索树中的众数
- 2019 年 11 月 3 日
- 筆記
题目描述
给定一个有相同值的二叉搜索树（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)
