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)

Tags:

VirMach 便宜 VPS