C++ BFS & DFS sols


  • 0
    M

    BFS solution - compute average level-by-level top-down. no need to save anything globally.

    public:
        vector<double> averageOfLevels(TreeNode* root) {
            vector<double> result;
            queue<const TreeNode*> q1, q2;
            q1.push(root);
            while(!q1.empty()) {
                double sum = 0, count = 0;
                while(!q1.empty()) {
                    const TreeNode* tmp = q1.front();
                    q1.pop();
                    sum += tmp->val;
                    count += 1;
                    if(tmp->left) q2.push(tmp->left);
                    if(tmp->right) q2.push(tmp->right);
                }
                swap(q1, q2);
                result.push_back(sum/count);
            }
            return result;
        }
    };
    

    DFS solution - cannot compute average (no complete info) at each level so need to keep a global memory and add to it on the fly (i.e. count and sum at each level)

    public:
        vector<double> averageOfLevels(TreeNode* root) {
            vector<pair<int, double>> count_sum;
            dfs(root, 0, count_sum);
            vector<double> result;
            for(const auto& p: count_sum)
                result.push_back(p.second/p.first);
            return result;
        }
    private:
        void dfs(const TreeNode* root, int level, vector<pair<int,double>>& count_sum) {
            if(!root) return;
            if(level==count_sum.size()) count_sum.push_back({0, 0});
            count_sum[level].first++;
            count_sum[level].second+=root->val;
            dfs(root->left, level+1, count_sum);
            dfs(root->right, level+1, count_sum);
        }
    };
    

Log in to reply
 

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