本次刷题日记的第 76 篇，力扣题为：515. 在每个树行中找最大值，中等
一、题目描述：
又是一个在二叉树中查找数据的题，515. 在每个树行中找最大值 ， 看看我们可以如何找
二、这道题考察了什么思想？你的思路是什么？
- 在每个树行中找最大值，给我们提出了哪些要求，具体来查看一下：
- 题目给出一颗二叉树，树上的节点存储的是整型的数字，有正数有负数
- 要求我们找到每一层的所有节点中的最大值，并存入结果集中，最后返回这棵树每一层的最大值节点值
分析
题目简洁，要求也很明确，实际上也很容易做
看到题目要求的是找到每一层的的最大值，其实第一反应还是想到的是层序遍历的方式，也就是广度优先算法来处理这道题
我们知道，是用广度优先算法遍历二叉树，实际上就是使用队列的方式，将二叉树的所有节点逐个加入到队列中，然后再逐个节点出队，知道队列为空，咱们就完成了一次二叉树的遍历
那么对应到本题，咱们需要如何去实现呢？
以前使用广度优先算法遍历二叉树，我们都是一个节点一个节点的入队和出队，这一次因为我们需要找到一层节点中的最大值
因此我们需要一层一层节点的出队，并计算最大值
从上图中，我们可以很清晰的知道，如果我们按照先让二叉树的左子树入队，再让右子树入队的话，那么就会上述我们看到的效果
当拿到每一层的所有节点的时候，计算最小值，岂不是一个很简单的事情了
那么，之前我们也说到过，能够使用深度优先算法的地方，必然是可以使用广度优先算法的，那么在这里也是同样的道理，能够使用广度优先算法的地方，必然也是可以使用深度优先算法的
关于 DFS 如何去实现这道题，兄弟们就可以思考一波
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
编码的时候需要注意的是，咱们出队需要一层一层的出队，然后再计算这一层中数值最大的一个节点，并加入到结果集
编码如下：
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func largestValues(root *TreeNode) []int { if root == nil{ return []int{} } // 保证 root 节点是有有效的 que := []*TreeNode{root} var res []int for len(que) > 0 { // 将每一层的节点都给到 tmp tmp := que que = nil maxVal := math.MinInt32 // 遍历 tmp ，且找到这一层的最大值 for _,node := range tmp { maxVal = max(maxVal, node.Val) if node.Left != nil{ que = append(que, node.Left) } if node.Right != nil { que = append(que, node.Right) } } res = append(res, maxVal) } return res } func max(a,b int) int { if a > b { return a } return b }
四、总结：
很明显，时间复杂度是 O(n) ，咱们使用广度优先算法，是将二叉树的每一个节点全部遍历了一遍
空间复杂度，这里我们可以看到，我们创建的 tmp 会存储每一层的节点数据，且 res 记录了每一层的最大值，总的来说，占用了 O(n) 级别的空间消耗，则空间复杂度是 O(n)
原题地址：515. 在每个树行中找最大值
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
