【刷题日记】515. 在每个树行中找最大值


theme: Chinese-red

持续创作,加速成长!这是我参与「掘金日新计划 · 6 月更文挑战」的第30天,点击查看活动详情

本次刷题日记的第 76 篇,力扣题为:515. 在每个树行中找最大值 ,中等

一、题目描述:

又是一个在二叉树中查找数据的题,515. 在每个树行中找最大值 , 看看我们可以如何找

二、这道题考察了什么思想?你的思路是什么?

  1. 在每个树行中找最大值,给我们提出了哪些要求,具体来查看一下:
  • 题目给出一颗二叉树,树上的节点存储的是整型的数字,有正数有负数
  • 要求我们找到每一层的所有节点中的最大值,并存入结果集中,最后返回这棵树每一层的最大值节点值

分析

题目简洁,要求也很明确,实际上也很容易做

看到题目要求的是找到每一层的的最大值,其实第一反应还是想到的是层序遍历的方式,也就是广度优先算法来处理这道题

我们知道,是用广度优先算法遍历二叉树,实际上就是使用队列的方式,将二叉树的所有节点逐个加入到队列中,然后再逐个节点出队,知道队列为空,咱们就完成了一次二叉树的遍历

那么对应到本题,咱们需要如何去实现呢?

以前使用广度优先算法遍历二叉树,我们都是一个节点一个节点的入队和出队,这一次因为我们需要找到一层节点中的最大值

因此我们需要一层一层节点的出队,并计算最大值

从上图中,我们可以很清晰的知道,如果我们按照先让二叉树的左子树入队,再让右子树入队的话,那么就会上述我们看到的效果

当拿到每一层的所有节点的时候,计算最小值,岂不是一个很简单的事情了

那么,之前我们也说到过,能够使用深度优先算法的地方,必然是可以使用广度优先算法的,那么在这里也是同样的道理,能够使用广度优先算法的地方,必然也是可以使用深度优先算法的

关于 DFS 如何去实现这道题,兄弟们就可以思考一波

三、编码

根据上述逻辑和分析,我们就可以翻译成如下代码

编码的时候需要注意的是,咱们出队需要一层一层的出队,然后再计算这一层中数值最大的一个节点,并加入到结果集

编码如下:

  1. /**
  2. * Definition for a binary tree node.
  3. * type TreeNode struct {
  4. * Val int
  5. * Left *TreeNode
  6. * Right *TreeNode
  7. * }
  8. */
  9. func largestValues(root *TreeNode) []int {
  10. if root == nil{
  11. return []int{}
  12. }
  13. // 保证 root 节点是有有效的
  14. que := []*TreeNode{root}
  15. var res []int
  16. for len(que) > 0 {
  17. // 将每一层的节点都给到 tmp
  18. tmp := que
  19. que = nil
  20. maxVal := math.MinInt32
  21. // 遍历 tmp ,且找到这一层的最大值
  22. for _,node := range tmp {
  23. maxVal = max(maxVal, node.Val)
  24. if node.Left != nil{
  25. que = append(que, node.Left)
  26. }
  27. if node.Right != nil {
  28. que = append(que, node.Right)
  29. }
  30. }
  31. res = append(res, maxVal)
  32. }
  33. return res
  34. }
  35. func max(a,b int) int {
  36. if a > b {
  37. return a
  38. }
  39. return b
  40. }

四、总结:

很明显,时间复杂度是 O(n) ,咱们使用广度优先算法,是将二叉树的每一个节点全部遍历了一遍

空间复杂度,这里我们可以看到,我们创建的 tmp 会存储每一层的节点数据,且 res 记录了每一层的最大值,总的来说,占用了 O(n) 级别的空间消耗,则空间复杂度是 O(n)

原题地址:515. 在每个树行中找最大值

今天就到这里,学习所得,若有偏差,还请斧正

欢迎点赞,关注,收藏

朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力

好了,本次就到这里

技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。

我是小魔童哪吒,欢迎点赞关注收藏,下次见~

暂时无法在飞书文档外展示此内容


文章标签:

原文连接:https://juejin.cn/post/7113361896404680740

相关推荐

翟佳:高可用、强一致、低延迟——BookKeeper的存储实现

管正雄:基于预训练模型、智能运维的QA生成算法落地

814. 二叉树剪枝 : 简单递归运用题

【综合笔试题】难度 3.5\u002F5,多解法热门二叉树笔试题

【java刷算法】牛客—剑指offer3栈、数组、递归、二分法的初步练习

leetcode 2342. Max Sum of a Pair With Equal Sum of Digits (python)

22张图带你深入剖析前缀、中缀、后缀表达式以及表达式求值

随机数索引(一题双解)【Leetcode每日(4.25)一题】C++

1260. 二维网格迁移 : 简单构造模拟题

坚持用C++刷牛客题(剑指offer专题)

日拱一卒,麻省理工教你信息安全和密码学

C语言——三种方式实现学生信息管理

快速排序及优化

萌新也能看懂的KMP算法

简答一波 HashMap 常见八股面试题 —— 算法系列(2)

素数算法(Prime Num Algorithm)

必须收藏!双目立体匹配算法:Patch Match Stereo实用详解教程

有哪些高质量的自学网站?

731. 我的日程安排表 II : 线段树(动态开点)的两种方式

LeetCode周赛302,这也太卷了,20分钟ak也只有300名……