Leetcode 501. 二叉搜索树中的众数

题目描述

给定一个有相同值的二叉搜索树（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)