前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 501. 二叉搜索树中的众数

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

作者头像
zhipingChen
发布2019-11-03 14:01:36
5730
发布2019-11-03 14:01:36
举报
文章被收录于专栏:编程理解

题目描述

给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。

假定 BST 有如下定义:

  • 结点左子树中所含结点的值小于等于当前结点的值
  • 结点右子树中所含结点的值大于等于当前结点的值
  • 左子树和右子树都是二叉搜索树

示例 1:

输入: 给定 BST [1,null,2,2]

代码语言:javascript
复制
          1
           \
            2
           /  
          2  

返回[2].

解法1

利用二叉搜索树特性

因为二叉搜索树的中序遍历为有序列表,所以相当于在有序列表中,取众数的值。所以只需要一次遍历即可获得每个元素的出现次数,即可获得众数。

代码语言:javascript
复制
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结果集中;若高于最大出现次数,则更新最大次数并清除结果集,重新添加当前元素。

代码语言:javascript
复制
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)
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档