1161. 最大层内元素和

题目描述：

给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。

请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。

测试用例：

示例 1:

输入：root = [1,7,0,7,-8,null,null]
输出：2
解释：
第 1 层各元素之和为 1，
第 2 层各元素之和为 7 + 0 = 7，
第 3 层各元素之和为 7 + -8 = -1，
所以我们返回第 2 层的层号，它的层内元素之和最大。

示例 2：

输入：root = [989,null,10250,98693,-89388,null,null,null,-32127]
输出：2

限制及提示：

• 树中的节点数在 [1, 10^4]范围内
• -10^5 <= Node.val <= 10^5

---

解题分析及思路：

本题与二叉树的遍历有关，可以采用层级遍历 🔗来进行解答

本题主要比较的是每一层的元素和，返回元素和最大的那一层，那么与层相关的采用层级遍历即可。

层级遍历使用的数据结构是队列，首先定义队列。

queue := []*TreeNode{root}

然后定义全局变量level、maxLevel、maxValue分别用来保存当前遍历层数、元素和最大值所对应的层数、元素和最大值

level := 0
maxLevel, maxValue := 1, math.MinInt

定义遍历当前层级的元素，如果有子节点直接追加到队列中，并且在遍历的同时累加，最后与maxValue比较即可

Func := func() {
    level++
    l := len(queue)
    value := 0
    for i := 0; i < l; i++ {
        node := queue[i]
        if node != nil {
            value += node.Val
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    if value > maxValue {
        maxValue = value
        maxLevel = level
    }
    queue = queue[l:]
}

因为不确定某一层是否还存在下一层，所以一直调用Func函数即可，直到所有节点遍历完成。

for len(queue) != 0 {
    Func()
}

复杂度：

• 时间复杂度：O(n)，遍历所有节点所需时间
• 空间复杂度：O(n)，存储所有节点所需空间

执行结果：

• 执行用时：92 ms, 在所有 Go 提交中击败了94.00%的用户
• 内存消耗：8.5 MB, 在所有 Go 提交中击败了6.00%的用户