Clean recursive solution in C++


  • 1
    class Solution {
    private:
        bool equal(TreeNode* l, TreeNode* r)
        {
            if(!l | !r) { if(!l && !r) return true; return false; }
            return l->val==r->val && equal(l->right, r->left) && equal(l->left, r->right);
        }
    public:
        bool isSymmetric(TreeNode* root) 
        {
            if(!root) return true;
            return equal(root->left, root->right);
        }
    };
    

  • 1

    An iterative solution is also enclosed here for reference.

    class Solution {
    public:
        bool isSymmetric(TreeNode* root) 
        {
            if(!root) return true;
            vector<TreeNode*> l, r;
            l.push_back(root->left);
            r.push_back(root->right);
            while(!l.empty())
            {
                vector<TreeNode*> l0, r0;
                int size = l.size();
                for(int i = 0; i < size; ++i)
                {
                    if(!l[i] || !r[size-i-1])
                    {
                        if(!l[i] && !r[size-i-1]) continue;
                        return false;
                    }
                    if(l[i]->val != r[size-i-1]->val) return false;
                    l0.push_back(l[i]->left);
                    l0.push_back(l[i]->right);
                    r0.push_back(r[size-i-1]->right);
                    r0.push_back(r[size-i-1]->left);
                }
                reverse(r0.begin(), r0.end());
                l = l0;
                r = r0;
            }
            return true;
        }
    };
    

Log in to reply
 

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