Iterative C++ solution using two queues (BFS)


  • 0
    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            if(root==nullptr)
                return true;
            queue<TreeNode*> leftQ;
            queue<TreeNode*> rightQ;
            leftQ.push(root->left);
            rightQ.push(root->right);
            while(!leftQ.empty() && !rightQ.empty()) {
                if(leftQ.size() != rightQ.size())
                    return false;
                int size = leftQ.size();
                while(size-- > 0) {
                    TreeNode* leftNode = leftQ.front(); leftQ.pop();
                    TreeNode* rightNode = rightQ.front(); rightQ.pop();
                    if(leftNode==nullptr && rightNode!=nullptr)
                        return false;
                    else if(leftNode!=nullptr && rightNode==nullptr)
                        return false;
                    else if(leftNode!=nullptr && rightNode!=nullptr) { 
                        if(leftNode->val != rightNode->val)
                            return false;
                        leftQ.push(leftNode->right);
                        leftQ.push(leftNode->left);
                        rightQ.push(rightNode->left);
                        rightQ.push(rightNode->right);
                    }
                }
            }
            return leftQ.empty() && rightQ.empty() ? true : false;
        }
    };

Log in to reply
 

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