[Binary Tree BFS][Easy] 637. Average of Levels in Binary Tree

Q. 주어진 Binary Tree의 level당 평균값을 구하고, 그 값을 출력하라. 

 

 

Solution

 BFS의 기본 문제. 

 각 level당 queue의 count를 이용해 레벨 노드의 정보를 얻어 결과 계산. 

 

 코드 

 

 

vector<double> averageOfLevels(TreeNode* root) 
{
    vector<double> vOut;
    if(root == nullptr)
        return vOut;
        
    queue<TreeNode*> qBuff;
    qBuff.push(root);
    while(qBuff.size() > 0)
    {
        int cnt = qBuff.size();
        double val = 0;
        for(int q = 0; q < cnt; ++q)
        {
            TreeNode* cur = qBuff.front();
            val += (double)(cur->val);
            qBuff.pop();

            if(cur->left != nullptr)    qBuff.push(cur->left);
            if(cur->right != nullptr)   qBuff.push(cur->right);
        }

        vOut.push_back( val / ((double)cnt) );
    }
    return vOut;    
}

 

 

결과.