C++ 4ms recursive DFS & iterative BFS 2 simple solutions


  • 0
    Z
    class Solution {
    public:
    bool isSymmetric(TreeNode* root) {
        //return solution1(root);     //recursive DFS
        return solution2(root);     //iterative BFS
    }
    private:
    bool solution1(TreeNode *root){
        if(!root) return true;
        return subSol1(root->left, root->right);
    }
    bool subSol1(TreeNode *left, TreeNode *right){
        if(!left && !right) return true;
        if(!left || !right) return false;
        if(left->val != right->val) return false;
        return subSol1(left->left, right->right) && subSol1(left->right, right->left);
    }
    bool solution2(TreeNode *root){
        if(!root) return true;
        if(!root->left && !root->right) return true;
        if(!root->left || !root->right) return false;
        queue<TreeNode *> q;
        q.push(root->left);
        q.push(root->right);
        TreeNode *left, *right;
        while(!q.empty()){
            if(q.size() % 2 == 1) return false;
            left = q.front();
            q.pop();
            right = q.front();
            q.pop();
            if(left->val != right->val) return false;
            if((!left->left && right->right) || (left->left && !right->right)) return false;
            if((!left->right && right->left) || (left->right && !right->left)) return false;
            if(left->left && right->right){
                q.push(left->left);
                q.push(right->right);
            }
            if(left->right && right->left){
                q.push(left->right);
                q.push(right->left);
            }
        }
        return true;
    }
    };

Log in to reply
 

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