1161. Maximum Level Sum of a Binary Tree

Leetcode link

题目简介

/**
 * @param {TreeNode} root
 * @return {number}
 */

题目给我们一个二叉树的根节点 root

要求我们将树的每一层加总，并且返回和最大且层数最小的层（根节点是第 1 层）

解题思路

需要把树的同一层元素值加总，我们使用 BFS 来做

在 BFS 的时候，我们需要 max 来表示当前最大的和是多少；curLayer 记录当前遍历到哪一层了

如果当前层的和大于 max，我们需要更新 max 与返回值 res

最后遍历结束后我们返回 res 即可

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxLevelSum = function (root) {
    const queue = [root]
    let max = Number.MIN_SAFE_INTEGER
    let curLayer = 1
    let res = 1

    while (queue.length > 0) {
        const size = queue.length
        let sum = 0

        for (let i = 0; i < size; i++) {
            const node = queue.shift()
            sum += node.val

            if(node.left) {
                queue.push(node.left)
            }
            if(node.right) {
                queue.push(node.right)
            }
        }
        if(sum > max) {
            res = curLayer
            max = sum
        }
        curLayer++
    }

    return res
};

复杂度分析

假设 n 代表树的节点个数

时间

因为我们需要遍历完完整的树，所以时间复杂度是 O(n)

空间

空间复杂度主要取决于 queue 数组，其复杂度为 O(w)，其中 w 代表树的最宽宽度

最坏的情况，会是 O(n)