BFS with two queues


  • 0
    G
    class Solution {    
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            // BFS with two queues - 'cur_q' and 'next_q'
            vector<vector<int>> r;              // result
            queue<TreeNode*> cur_q, next_q;     // representing current row and next row
            if (root != NULL) {
                cur_q.push(root);
            }
            int row = 0;
            do {
                // process elements at current row
                // insert them into the results vector at 'row'-th index
                // insert all their children into the next row
                while (!cur_q.empty()) {
                    TreeNode* node = cur_q.front();
                    cur_q.pop();
                    if (r.size() == row) {
                        r.push_back(vector<int>());
                    }
                    r[row].push_back(node->val);
                    if (node->left != NULL) {
                        next_q.push(node->left);
                    }
                    if (node->right != NULL) {
                        next_q.push(node->right);
                    }
                }
                row++;
                // make 'next_q' as 'cur_q'
                cur_q = next_q;
                while (!next_q.empty()) {
                    next_q.pop();        // delete all elements in 'next_q'
                }
            } while (!cur_q.empty());
            return r;
        }
    };
    

Log in to reply
 

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