30daysOfCode/29-09-23-AverageOfLevelsBinaryTree.cpp at main · MatheusSanchez/30daysOfCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
Time: O(n);
Space: O(2^k); k == altura da arvore
https://leetcode.com/problems/average-of-levels-in-binary-tree/description/
*/

class Solution {
   public:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> q;
        vector<double> ans;
        double howMany = 1;
        double nextLevel = 0;
        q.push(root);
        double actualSum = 0;

        while (!q.empty()) {
            nextLevel = 0;
            actualSum = 0;

            for (int i = 0; i < howMany; i++) {
                TreeNode* auxiliar = q.front();
                actualSum += auxiliar->val;
                q.pop();
                if (auxiliar->left != NULL) {
                    nextLevel++;
                    q.push(auxiliar->left);
                }
                if (auxiliar->right != NULL) {
                    nextLevel++;
                    q.push(auxiliar->right);
                }
            }

            ans.push_back(actualSum / howMany);

            howMany = nextLevel;
        }

        return ans;
    }
};