C++, BFS


  • 0
    Z

    This is a simply level order traversal using BFS and queue. Time complexity O(n).

    class Solution {
    public:
        vector<double> averageOfLevels(TreeNode* root) {
            vector<double> ans;
            if (root == NULL) return ans;
            queue<TreeNode*> myq;
            myq.push(root);
            while (!myq.empty()) {
                int n = myq.size();
                double sum = 0.0;
                for (int i = 0; i < n; i++) {
                    TreeNode* p = myq.front();
                    myq.pop();
                    sum += p->val;
                    if (p->left) myq.push(p->left);
                    if (p->right) myq.push(p->right);
                }
                ans.push_back(sum/n);
            }
            return ans;
        }
    };
    

Log in to reply
 

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