C++ Solution using Queue - Runtime beats 82.13% of Solutions


  • 0
    S

    The solution uses two queues. Runtime beats 82.13 % of cpp submissions.

    class Solution {
    public:
        vector<double> averageOfLevels(TreeNode* root) {
            if(!root) {return {};}
            queue<TreeNode*> q1,q2; vector<double> vec;
            q1.push(root);
            while(!q1.empty() || !q2.empty()){
                vec.push_back(avg(q1,q2));
            }
            return vec;
        }
        double avg(queue<TreeNode*> &q1, queue<TreeNode*> &q2){
            double count=0,sum=0; TreeNode *temp;
            if(q1.empty()){
                while(!q2.empty()){
                    temp=q2.front(); q2.pop(); ++count; sum+=temp->val;
                    if(temp->left){ q1.push(temp->left);}
                    if(temp->right){ q1.push(temp->right);}
                }
                return (sum/count);
            }
             if(q2.empty()){
                while(!q1.empty()){
                    temp=q1.front(); q1.pop(); ++count; sum+=temp->val;
                    if(temp->left){ q2.push(temp->left);}
                    if(temp->right){ q2.push(temp->right);}
                }
                return (sum/count);
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.