Share my C++ code using deque to implement BFS


  • 1
    X
    class Solution 
    {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) 
        {
            vector<vector<int>> res;
            if(root == NULL)    return res;
            deque<TreeNode*> dq;
            dq.push_back(root);
            int nums_nowlayer, nums_nextlayer = 1;
            while(!dq.empty())
            {
                nums_nowlayer = nums_nextlayer;
                nums_nextlayer = 0;
                
                vector<int> val(nums_nowlayer);
                int idx = 0;
                // deal with the ith layer
                while(nums_nowlayer--)
                {
                    // get the queue first element
                    TreeNode* r = dq.front();
                    val[idx++] = r->val;
                    if(r->left != NULL)
                    {
                        dq.push_back(r->left);
                        ++ nums_nextlayer;
                    }
                    if(r->right != NULL)
                    {
                        dq.push_back(r->right);
                        ++ nums_nextlayer;
                    }
                    dq.pop_front();
                }
                res.push_back(val);
            }
            return res;
        }
    };

  • 0
    L

    6666666666, feng ge


  • 0
    X

    Memeda. Paizuo! I am looking forward to your return.


Log in to reply
 

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