leetcode 637. Average of Levels in Binary Tree

Myth丶恋晨 2022-06-09 09:25 161阅读 0赞

# 1.题目 #

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:  
Input:

3
       / \
      9  20
        /  \
       15   7

Output: \[3, 14.5, 11\]  
Explanation:  
The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return \[3, 14.5, 11\].

注意每个节点上的值为32位有符号整数  
Note:  
The range of node’s value is in the range of 32-bit signed integer.

# 2.分析 #

广度优先遍历，对每一层的节点值求和，再取平均值。  
注意：由于节点值32位整数，求和如果用int保存会溢出，而平均值是double类型。所以用double来保存求和

# 3.代码 #

vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> nodes;
        nodes.push(root);
        vector<double> ans;
        while (!nodes.empty()) {
            int n = nodes.size();
            int sum = 0;
            for (int i = 0; i < n; i++) {
                TreeNode* node = nodes.front();
                sum += node->val;
                nodes.pop();
                if(node->left)
                    nodes.push(node->left);
                if(node->right)
                    nodes.push(node->right);
            }
            ans.push_back((double)sum / n);
        }
        return ans;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，161人围观）

还没有评论，来说两句吧...

相关阅读

相关（Java）leetcode-637 Average of Levels in Binary Tree (二叉树的层平均值)

题目描述 Given a non-empty binary tree, return the average value of the nodes on each lev

r囧r小猫/ 2023年02月16日 01:46/ 0 赞/ 121 阅读

相关 LeetCode - Easy - 637. Average of Levels in Binary Tree

Topic Tree Description [https://leetcode.com/problems/average-of-levels-in-bin

古城微笑少年丶/ 2022年10月16日 09:39/ 0 赞/ 139 阅读

相关 leetcode 637. Average of Levels in Binary Tree | 637. 二叉树的层平均值（Java）

题目 [https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/][https_leetcod

我会带着你远行/ 2022年10月05日 02:57/ 0 赞/ 133 阅读

相关 LeetCode--Binary Tree Level Order Traversal

Problem: > Given a binary tree, return the level order traversal of its nodes’ values.

小鱼儿/ 2022年08月18日 01:55/ 0 赞/ 26 阅读

相关 Binary Tree Level Order Traversal--LeetCode

题目： Given a binary tree, return the level order traversal of its nodes' values. (ie,

不念不忘少年蓝@/ 2022年08月07日 11:56/ 0 赞/ 29 阅读

相关 LeetCode-Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from le

你的名字/ 2022年08月04日 00:58/ 0 赞/ 46 阅读

相关 leetcode 637. Average of Levels in Binary Tree

1.题目 Given a non-empty binary tree, return the average value of the nodes on each lev

Myth丶恋晨/ 2022年06月09日 09:25/ 0 赞/ 162 阅读

相关 637. Average of Levels in Binary Tree

题目描述： Given a non-empty binary tree, return the average value of the nodes on each leve

た入场券/ 2022年06月08日 14:09/ 0 赞/ 164 阅读

相关 leetcode 637. Average of Levels in Binary Tree 二叉树每层平均值+广度优先遍历BFS

Given a non-empty binary tree, return the average value of the nodes on each level in th

￡神魔★判官ぃ/ 2022年06月03日 05:38/ 0 赞/ 169 阅读

相关 637. Average of Levels in Binary Tree

[原题链接][Link 1] 主要考察的是对树这个数据结构的遍历。这里有两种方式 BFS 在这种题目上来说，使用BFS进行层次遍历进行代码的书写更舒服 pub

心已赠人/ 2022年06月02日 00:26/ 0 赞/ 121 阅读