每日一题(LeetCode)----二叉树--二叉树的层平均值

每日一题(LeetCode)----二叉树–二叉树的层平均值

1.题目（637. 二叉树的层平均值）

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

  示例 1：

  

  输入：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:

  

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

  提示：

  • 树中节点数量在 [1, 104] 范围内
  • -231 <= Node.val <= 231 - 1

2.解题思路

思路一：层序遍历

1.使用一个队列 其中元素的类型为node类型的指针（这里的队列我们用的是c++中封装好的，其实是模板类，我们这里是通过模板类创建了一个对象）和一个结果数组，结果数组用来存最终的结果

2.定义一个变量来记录当前层元素的个数（每出列一个元素都更新），再定义一个变量用来记录当前层总和和另一个变量用来记录当前层元素总数（当当前层元素都遍历完时，进行更新）

3.初始时，我们将根节点放入到队列中去，当前层元素个数记为1（提示：每出队列一个元素，那么当前层元素的个数进行-1操作）

4.我们将队列中的首元素出列，并将其不为空的左孩子和右孩子入队，然后当前层总和加上当前节点的值，当前层元素个数-1，当当前层元素个数变为0时，我们将当前层总和除以当前层元素总数的值放入到我们的结果数组中，并获取下一层元素个数，下一层元素的总数重复这个操作，直到队列为空结束

5.返回结果数组

3.写出代码

思路一的代码

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> res;
        if(root==nullptr){
            return res;
        }
        queue<TreeNode*> qe;
        int t=0;
        qe.push(root);
        t=1;
        int x=t;
        double num=0;
        while(!qe.empty()){
            TreeNode* temp=qe.front();
            num+=temp->val;
            qe.pop();
            if(temp!=nullptr&&temp->left!=nullptr){
                qe.push(temp->left);
            }
            if(temp!=nullptr&&temp->right!=nullptr){
                qe.push(temp->right);
            }
            t--;
            if(t==0){
                res.push_back(num/=x);
                num=0;
                t=qe.size();
                x=t;
            }

        }

        return res;
    }
};