LeetCode 637. Average of Levels in Binary Tree(层序遍历）

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

Example 1:

<b>Input:</b>

    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].

Note:

The range of node’s value is in the range of 32-bit signed integer.

分析

树的层序遍历

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

   vector<double> averageOfLevels(TreeNode* root) {

          vector<double> res;

          double sum=0,cnt=0;

          queue<TreeNode*> q;

          q.push(root);

          TreeNode* last=root;

          TreeNode* tail;

          while(!q.empty()){

               TreeNode* t=q.front();

               q.pop();

               sum+=t->val;

               cnt++;

               if(t->left!=NULL){

                   q.push(t->left);

                   tail=t->left;

               }

               if(t->right!=NULL){

                   q.push(t->right);

                   tail=t->right;

               }

               if(t==last){

                  last=tail;

                  res.push_back(sum/cnt);

                  sum=cnt=0;

               }

          }

        return res;

    }

};

巴特西

LeetCode 637. Average of Levels in Binary Tree(层序遍历）

最新文章

热门文章