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

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

28 人参与  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