C++ 3ms two deque level traversal


  • 0
     bool isSymmetric(TreeNode* root) {
            if(root==NULL) return true;
            deque<TreeNode*>q; //Current level
            deque<TreeNode*>sub; //Next level
            if(root->left!=NULL) q.push_back(root->left);
            if(root->right!=NULL) q.push_back(root->right);
            while(!q.empty()){
                TreeNode* head=q.front();
                q.pop_front();
                if(q.empty()) return false;
                TreeNode* tail=q.back();
                q.pop_back();
                if(head->val!=tail->val) return false;
                if(head->right!=NULL){ 
                    if(tail->left!=NULL) sub.push_front(head->right),sub.push_back(tail->left);
                    else return false;
                }else if(tail->left!=NULL) return false;
                if(head->left!=NULL){
                    if(tail->right!=NULL) sub.push_front(head->left),sub.push_back(tail->right);
                    else return false;
                }else if(tail->right!=NULL) return false;
                if(q.empty()) q=sub,sub.clear(); //Go to next level
            }
            return true;
        }
    

    Modified Version

    bool isSymmetric(TreeNode* root) {
                ...
                if(head->right==NULL||tail->left==NULL){ if(head->right!=tail->left) return false;}
                else sub.push_front(head->right),sub.push_back(tail->left);
                if(head->left==NULL||tail->right==NULL){ if(head->left!=tail->right) return false;}
                else sub.push_front(head->left),sub.push_back(tail->right);
                ...
        }
    

Log in to reply
 

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