Share my 3ms C++ BFS using two queues, easy to understand


  • 0
    L

    DFS has been discussed a lot, it's simple and concise for many people, but if you're not good at recursion, BFS would be a good choice, 'cause it's mainly based on iteration.
    I use two queues(in fact can be treated as a deque, but deque is much slower in efficiency) to deal with the left side and right side, each time enqueue thier children and compare, if there's any pair unequal, return false.
    The following code:

    if((start->left!=NULL&&end->right==NULL)||(start->right!=NULL&&end->left==NULL))return false;
    

    is quite important, because the comparison must keep symmetric.

    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            //BFS method
            if(!root)
                return true;
            queue<TreeNode*> q1;
            queue<TreeNode*> q2;
            q1.push(root);
            q2.push(root);
            while(!q1.empty()||!q2.empty()){
                for(int i=0,n1=q1.size(),n2=q2.size();n1==n2&&i<n1;i++){
                    TreeNode* start=q1.front();
                    TreeNode* end=q2.front();
                    q1.pop();
                    q2.pop();
                    if((start->val)!=(end->val))
                        return false;
                    if((start->left!=NULL&&end->right==NULL)||(start->right!=NULL&&end->left==NULL))
                        return false;
                    if(start->left)
                        q1.push(start->left);
                    if(end->right)
                        q2.push(end->right);
                    if(start->right)
                        q1.push(start->right);
                    if(end->left)
                        q2.push(end->left);
                }
            }
            return true;
        }
    };
    

Log in to reply
 

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