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

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

21 人参与  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://zhangshiyu.com/post/38274.html

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

  • 评论(0)
  • 赞助本站

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

最新文章

  • 她的记忆停留在了最爱初恋的那年许欣柔楚临川完本_她的记忆停留在了最爱初恋的那年(许欣柔楚临川)
  • 全书浏览假千金的实习生男友霸占我办公室,我反手让他们倾家荡产(顾家明)_假千金的实习生男友霸占我办公室,我反手让他们倾家荡产(顾家明)全书结局
  • 童养夫让我给他的新欢出修复费(林嘉芝林思雅)_童养夫让我给他的新欢出修复费林嘉芝林思雅
  • 全文资助生女婿让我给他白月光付三千万月子中心钱(宋清玉宋雅)列表_全文资助生女婿让我给他白月光付三千万月子中心钱
  • 碎在时光里的谎言喻景宴秦明月完本_碎在时光里的谎言(喻景宴秦明月)
  • 旧爱剜心吻成灰席鄢之岑秋全书免费旧爱剜心吻成灰席鄢之岑秋全书免费
  • 结婚六年丈夫不碰我谁知儿子亲爹是寡头(纪清言傅司砚),结婚六年丈夫不碰我谁知儿子亲爹是寡头
  • 老公想换掉我的男胎,我笑他自不量力(宋薇于继业)_老公想换掉我的男胎,我笑他自不量力宋薇于继业
  • 给太子下了噬心蛊后,皇后找上门(小夭赵劼)全书浏览_给太子下了噬心蛊后,皇后找上门全书浏览
  • 豪门绝嗣!带球跑的夫人回来了!(谢长宴慕清杳)_豪门绝嗣!带球跑的夫人回来了!谢长宴慕清杳
  • 完美身材(李朵林之晴)_完美身材李朵林之晴
  • 离婚后,我和快穿系统绑定(白意秋陈荣周立慧)_离婚后,我和快穿系统绑定(白意秋陈荣周立慧)

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

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