本次刷题日记的第 95 篇，力扣题为：1302. 层数最深叶子节点的和
一、题目描述：
又是一个二叉树类型的题目，看看需要咱们如何来解决它
二、这道题考察了什么思想？你的思路是什么？
题目要求咱们找层数最深的叶子节点的和
题目的要求很明确，咱们需要注意的点有这些：
- 题目要求找深度最深的叶子节点，那么八成是需要使用深度优先算法来进行处理的
- 求解深度最深的叶子节点的和，也就意味着，第一我们要先找到二叉树的最深深度是多少，并且对于这一层上的节点有多少个即取他们的和即可
分析
其实仔细看来，自然是咱们可以有 2 种二叉树遍历方式来处理这个题，如果是使用层序遍历的话，会更加形象
如果咱们是使用层序遍历的方式来处理题目的话，实际上就直接正常遍历二叉树即可，遍历到最后一层的时候，直接闭着眼睛将这最后一层节点相加即可得到结果，例如这样
层序遍历的时候，咱们一般是使用队列的方式来进行处理，将每一层的节点挨个全部放到队列中，然后全部取出进行遍历，再将下一层的所有节点全部加入到队列中，循环往复，直到队列为空，咱们直接就将最后一层的节点全部取出来求和即可
那么深度优先遍历二叉树的话我们又需要如何去处理呢？
深度优先，我们知道，咋是从 root 节点开始，不停的去一层一层的递归，那么这个时候，咱们可以零 root 节点这一层深度为 0，那么往下递归一层深度就 +1，且这个时候咱们使用一个变量 maxLevel 看来记录当前的最大层，若更新这个最大层，则 sum 直接赋值为当前节点的值，若节点递归的时候，等于最大层，那么就sum += 当前节点的值
这样的思考方式和实现方式，如果一直在递归，maxLevel 的值一直在增大，那么 sum 的值一直在被刷新，只有当找到树的最大层的时候，sum 才会开始相加，则最终遍历完毕后， sum 即为深度最深的的叶子节点的和了
例如咱们遍历二叉树，使用 前序遍历的方式
就这么来看，咱们的如上两种方式，广度优先算法，深度优先算法 来处理这个题，接下来咱们就来手撸代码吧，写一个深度优先算法的
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
- 使用深度优先算法的话，咱们需要记录当前节点所在的层次
编码如下：
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func deepestLeavesSum(root *TreeNode) (sum int) { maxLevel := -1 var dfs func(*TreeNode, int) dfs = func(node *TreeNode, level int) { if node == nil { return } if level > maxLevel { maxLevel = level sum = node.Val } else if level == maxLevel { sum += node.Val } dfs(node.Left, level+1) dfs(node.Right, level+1) } dfs(root, 0) return }
四、总结：
咱们这种处理方式的时间复杂度是 O(n) ，具体是因为咱们的递归了所有了节点才能得出结果，因此是 O(n)
空间复杂度也是 O(n) ，因此咱们的递归是需要消耗栈空间的
原题地址：1302. 层数最深叶子节点的和
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
