( “树” 之 BFS) 637. 二叉树的层平均值 ——【Leetcode每日一题】

比眉伴天荒 2024-03-23 14:15 74阅读 0赞

### 637. 二叉树的层平均值 ###

给定一个非空二叉树的根节点 `root` , 以数组的形式返回每一层节点的平均值。与实际答案相差  1 0 − 5 10^\{-5\} 10−5 以内的答案可以被接受。

##### 示例 1： #####

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

> 输入：root = \[3,9,20,null,null,15,7\]  
> 输出：\[3.00000,14.50000,11.00000\]  
> 解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。  
> 因此返回 \[3, 14.5, 11\] 。

##### 示例 2: #####

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

> 输入：root = \[3,9,20,15,7\]  
> 输出：\[3.00000,14.50000,11.00000\]

**提示：**

*  树中节点数量在  \[ 1 , 1 0 4 \] \[1, 10^4\] \[1,104\] 范围内
 *   − 2 31 < = N o d e . v a l < = 2 31 − 1 -2^\{31\} <= Node.val <= 2^\{31\} - 1 −231<=Node.val<=231−1

#### 思路：BFS ####

使用 BFS 进行层次遍历。

不需要使用两个队列来分别存储当前层的节点和下一层的节点

*  因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。

#### 代码：(Java、C++) ####

**Java**

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<Double> averageOfLevels(TreeNode root) {
        
            List<Double> ans = new ArrayList<>();
            Queue<TreeNode> que = new LinkedList<>();
            que.add(root);
            while(!que.isEmpty()){
        
                int len = que.size();
                double sum = 0;
                for(int i = 0; i < len; i++){
        
                    root = que.poll();
                    sum += root.val;
                    if(root.left != null) que.add(root.left);
                    if(root.right != null) que.add(root.right);
                }
                ans.add(sum / len);
            }
            return ans;
        }
    }

**C++**

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
        
    public:
        vector<double> averageOfLevels(TreeNode* root) {
        
            vector<double> ans;
            queue<TreeNode*> que;
            que.push(root);
            while(!que.empty()){
        
                int len = que.size();
                double sum = 0;
                for(int i = 0; i < len; i++){
        
                    root = que.front();
                    que.pop();//pop返回的是void
                    sum += root->val;
                    if(root->left != NULL) que.push(root->left);
                    if(root->right != NULL) que.push(root->right);
                }
                ans.push_back(sum / len);
            }
            return ans;
        }
    };

##### 运行结果： #####

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

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n)，其中 `n` 是二叉树中的节点个数。 广度优先搜索需要对每个节点访问一次，时间复杂度是  O ( n ) O(n) O(n)。 需要对二叉树的每一层计算平均值，时间复杂度是  O ( h ) O(h) O(h)，其中 `h` 是二叉树的高度，任何情况下都满足  h ≤ n h≤n h≤n。 因此总时间复杂度是 O ( n ) O(n) O(n)。
 *  **空间复杂度**： O ( n ) O(n) O(n)，其中 `n` 是二叉树中的节点个数。空间复杂度取决于队列开销，队列中的节点个数不会超过 `n`。

题目来源：[力扣。][Link 1]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[b00c8f48de4147be8363779f748b8e44.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/c03e4c61bb8142418746b534dd22c0b9.png
[d51ff66000f848f581513f4f50e9829b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/1e2a80d1aaf4483ebc2fc3aa70d64073.png
[dfbfdb02dfd5407088e11bbc36ae1d53.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/2c9e9145906d4829939e90a20696a318.png
[Link 1]: https://leetcode.cn/problems/average-of-levels-in-binary-tree/description/
[leetCode]: http://t.csdn.cn/kQLJO