[LeetCode]637. 두 갈래 나무의 층 평균치

제목

 ,  .

  1:

 :
    3
   / \
  9  20
    /  \
   15   7
 : [3, 14.5, 11]
 :
 0  3,   1  14.5,  2  11.   [3, 14.5, 11].
 ：

 32 。

코드

/**
 * 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> results;
        queue que;
        que.push(root);
        int oldNodeCount=1;
        int levelCount=1;
        int newNodeCount=0;
        double levelAverage=0.0;
        while(que.size()!=0)
        {
            TreeNode* node=que.front();
            que.pop();
            oldNodeCount--;
            levelAverage+=node->val;
            if(node->left!=NULL)
            {
                que.push(node->left);
                newNodeCount++;
            }
            if(node->right!=NULL)
            {
                que.push(node->right);
                newNodeCount++;
            }
            if(oldNodeCount==0)
            {
                results.push_back(levelAverage/levelCount);
                levelCount=newNodeCount;
                oldNodeCount=newNodeCount;
                newNodeCount=0;
                levelAverage=0.0;
            }
        }
        return results;
    }
};

생각

이 해법은 차원 반복을 바탕으로 나의 사고방식은 하나의 보조 대기열로 결점을 보존하고 두 변수로 현재 층의 결점 개수와 다음 층의 결점 개수를 보존하는 것이다.대기열 헤드 결점을 반복할 때마다 현재 결점 개수-1, 그리고 이 결점의 하위 노드를 반복합니다. 비어 있지 않으면 대기열을 추가하고 다음 결점 개수+1, 앞층 결점 개수가 0일 때 현재 층이 반복적으로 완성되면 다음 결점 개수는 현재 층 결점 개수로 변하고 다음 층 결점 개수는 0을 계산하여 대기열의 원소 개수가 0이 될 때까지 계속 반복합니다.