(Easy - BFS) Leetcode - 637. Average of Levels in Binary Tree

이진 트리가 주어졌을 때 각 Level의 노드의 값의 평균을 찾는 문제입니다.

Level 단위로 노드를 방문해야 하기에 인접한 노드들을 방문하는 너비우선탐색인 BFS를 사용해 문제를 풀어야 합니다.

 

queue를 사용해 문제를 풀었습니다.

큐에 root 노드를 넣어주면 큐에 Level 0의 모든 노드를 넣은 셈이 되는데 이때 큐의 크기가 1이 됩니다.

이는 Level 0에 있는 모든 노드의 개수과 동일합니다.

이후 큐에 저장된 노드를 사용해 자식 노드들을 큐에 다시 저장하면 큐에는 Level 1의 노드들만 들어가게 됩니다.

그러면 현재 큐의 크기는 Level 1의 노드의 개수와 같습니다.

이런 특징을 사용해 각 Level의 값의 평균을 구해줍니다.

 

이 방식을 더이상 방문할 노드가 없을때까지 반복해줍니다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> ans;
        std::queue<TreeNode*> q;
        q.push(root); // Level 0인 root 노드부터 시작
        
        while (!q.empty()) {
            int levelSize = q.size(); // 현재 Level의 노드 수
            
            double sum = 0; // 현재 Level에 있는 노드들의 값의 합
            for (int i = 0; i < levelSize; i++) {
                TreeNode* cur = q.front(); // 현재 Level에 있는 노드들을 하나씩 방문
                q.pop();

                // 자식 노드가 있다면 큐에 추가 (다음 Level의 노드들)
                if (cur->left)
                    q.push(cur->left);
                if (cur->right)
                    q.push(cur->right);
                
                sum += cur->val; // 노드의 값의 합
            }

            ans.push_back(sum / levelSize); // 현재 Level의 평균
        }

        return ans;
    }