当前位置:首页 » 《随便一记》 » 正文

【二叉树】二叉搜索树中的众数_豪冷的博客

4 人参与  2022年04月17日 15:41  分类 : 《随便一记》  评论

点击全文阅读


0x00 题目

给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)
如果众数超过 1 个,不需考虑输出顺序

进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)


0x01 思路

二叉搜索树的 中序遍历 是一个升序数组

可以把遍历结果放在一个 字典 里面
再遍历,根据 数量 来确定

时间复杂度: O(N)
空间复杂度: O(N)


此外
还可以顺序扫描【中序遍历】序列
base 记录当前的数字
count 记录当前数字重复的次数
maxCount 来维护已经扫描过的数当中,出现最多的那个数字的出现次数
res 数组记录出现的众数

时间复杂度: O(N)
空间复杂度: O(1)


0x02 解法

语言:Swift

树节点:TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

中序遍历 解法:

func findMode(_ root: TreeNode?) -> [Int] {
    var res: [Int] = []
    var base = 0
    var count = 0
    var maxCount = 0
    
    func find(_ root: TreeNode?) {
        guard let root = root else { return }
        
        // 前序遍历位置
        find(root.left)
        
        // 中序遍历位置
        
        let val = root.val
        // 值一样,数量加1
        if val == base { count += 1}
        // 值不一样,重置
        else { count = 1; base = val }

        // 数量一样,添加
        if count == maxCount {
            res.append(val)
        }
        // 数量不一样,重置
        else if count > maxCount {
            maxCount = count
            res.removeAll()
            res.append(val)
        }
        
        find(root.right)
        // 后序遍历位置
    }
    
    find(root)
    return res
}


五笔学习

小程序:XWubi
配合公众号文章一起食用,效果更佳~
五笔教程之字根解析(四)
请添加图片描述



点击全文阅读


本文链接:http://m.zhangshiyu.com/post/38274.html

遍历  复杂度  数量  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 全书浏览重生高考填报志愿时我放任全班上大专+后续(叶淼淼宋津年颜禾晚)_重生高考填报志愿时我放任全班上大专+后续(叶淼淼宋津年颜禾晚)全书结局
  • 他的甜撩藏不住附加黎初谢时晏:结局+番外免费品鉴(他的甜撩藏不住)全本浏览阅读连载中
  • 全文他死遁后逼疯清冷女权臣+完结+后续(苏煜顾宛柔)列表_全文他死遁后逼疯清冷女权臣+完结+后续
  • 暑假毕业旅游,班花将我们身份证交给黑导游(江诗晗)全书浏览_暑假毕业旅游,班花将我们身份证交给黑导游全书浏览
  • 重生到高考前,我放任竹马为爱私奔新上热文_裴文远柳雨文远完结版_小说后续在线阅读_无删减免费完结_
  • 雨织离歌浮生浅节选_沈翊鸣苏之雨小姐完整文本_小说后续在线阅读_无删减免费完结_
  • 鬓边不是牡丹红精选(盛惟芳萧既明贺锦)_鬓边不是牡丹红精选盛惟芳萧既明贺锦
  • 宋岑月傅忠焜:结局+番外免费品鉴:结局+番外评价五颗星
  • 桑榆非晚半春休,姜晚榆沈淮遇完本_完本桑榆非晚半春休,姜晚榆沈淮遇
  • 大逃杀游戏老公一千万赌我死人气节选(萧铎纪云笙白茵茵)全书浏览_大逃杀游戏老公一千万赌我死人气节选全书浏览
  • 黎初谢时晏(他的甜撩藏不住)后续+番外精编之作_黎初谢时晏(他的甜撩藏不住)免费在线阅读无删减_笔趣阁
  • 把自己上交国家,龙神崽崽旺全国龙小小小说整本+后续(龙小小)清爽版阅读

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1