Recursive and non-recursive solution in C++: easy to understand


  • 0
    S

    Recursive one.

    class Solution {
        // check whether a tree is the mirror of another one
        bool isMirror(const TreeNode* root1, const TreeNode* root2){
            if (root1 == nullptr && root2 == nullptr)
                return true;
            if ((root1 == nullptr && root2 != nullptr) ||
                (root1 != nullptr && root2 == nullptr)){
                    return false;
                }
            // both non-nullptr
            return (root1->val == root2->val) 
                && isMirror(root1->left, root2->right) 
                && isMirror(root1->right, root2->left);
        }
        
    public:
        bool isSymmetric(TreeNode* root) {
            if (root == nullptr)
                return true;
            return isMirror(root->left, root->right);
        }
    };
    

    Non-recursive: simply replace the "system call" stack with a manual one.

    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            if (root == nullptr)
                return true;
            std::stack<TreeNode*> s;
            s.push(root->left);
            s.push(root->right);
            while (!s.empty()){
                
                auto root1 = s.top();
                s.pop();
                auto root2 = s.top();
                s.pop();
                if (root1 == nullptr && root2 == nullptr)
                    continue;
                if ((root1 == nullptr && root2 != nullptr) ||
                    (root1 != nullptr && root2 == nullptr))
                    return false;
                if (root1->val != root2->val)
                    return false;
                s.push(root2->left);
                s.push(root1->right);
                s.push(root2->right);
                s.push(root1->left);
            }
            return true;
        }
    };
    

Log in to reply
 

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