[LeetCode] 637. Average of Levels in Binary Tree c++

• 문제

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10^-5 of the actual answer will be accepted.

출처 : https://leetcode.com/problems/average-of-levels-in-binary-tree/

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
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].

같은 depth에 있는 node들의 평균 값을 구해서 vector에 저장하는 문제이다.

 

• 문제 해결

1. qlen으로 현재 depth 노드들의 개수를 구한다.

2. qlen 만큼 반복문을 돌려 해당 depth의 노드들의 합인 sum을 구한다.

3. 다음 depth의 평균값을 구하기 위해 LC(Left Child), RC(Right Child)를 queue 에 삽입한다.

4. 반복문이 끝나면 평균값을 구하기 위해 sum / qlen 식을 수행한다.

vector<double> averageOfLevels(TreeNode* root) {

    queue<TreeNode* > que;
    que.push(root);

    vector<double> ans;
    while (que.size()) {
        double qlen = que.size(), sum = 0;
        for (int i = 0; i < qlen; i++) {
            TreeNode* curr = que.front();
            que.pop();
            sum += curr->val;
            if (curr->left) {
                que.push(curr->left);
            }
            if (curr->right) {
                que.push(curr->right);
            }
        }
        double tmp = sum / qlen;

        ans.push_back(sum / qlen);
    }
    return ans;
}