【LeetCode 637】二叉树的层平均值

蔚落 2022-12-06 04:20 146阅读 0赞

#### 题目描述 ####

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

示例 1：

输入：
        3
       / \
      9  20
        /  \
       15   7
    输出：[3, 14.5, 11]
    解释：
    第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

提示：

节点值的范围在32位有符号整数范围内。

#### 解题思路 ####

这是LeetCode今天的每日一题，是一道比较简单的题目，就是二叉树的层序遍历。这里使用BFS（广度优先遍历），在遍历的过程中，将每层的节点值保存在队列中，然后将所有值出栈并相加。除以当前层的队列的长度就是这一层的平均值。将其放入结果中。重复上述步骤，直到遍历完整棵二叉树，返回最后的结果。

#### 代码实现 ####

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */
    /** * @param {TreeNode} root * @return {number[]} */
    var averageOfLevels = function(root) { 
        if(!root){ 
            return []
        }
        const res = []
        const queue = []
    
        queue.push(root)
        
        while(queue.length){ 
            const len = queue.length
            let sum = 0
            for(let i = 0; i < len; i++){ 
                const cur = queue.shift()
                sum += cur.val
                if(cur.left){ 
                    queue.push(cur.left)
                }
                if(cur.right){ 
                    queue.push(cur.right)
                }
            }
            res.push(sum / len)
        }
        return res
    };

#### 提交结果 ####

![在这里插入图片描述][20200912130101128.png]

[20200912130101128.png]: /images/20221123/469a8f701ba94e90a44ba14099b3a905.png?