Recursive solution and iterative solution share. [python]


  • 0
    L

    this problem is interesting,

    and I want to share my solution.

    class Solution:
    # @param root, a tree node
    # @return a boolean
    def isSymmetric2(self, root):
        def isSymmNodes(a,b):
            if(a==None and b==None):return True;
            elif(a!=None and b==None):return False;
            elif(b!=None and a==None):return False;
            else:
                if(a.val == b.val):
                    al=a.left.val if a.left!=None else None;
                    ar=a.right.val if a.right!=None else None;
                    bl=b.left.val if b.left!=None else None;
                    br=b.right.val if b.right!=None else None;
                    if(al==br and ar==bl):
                        t1,t2=True,True;
                        if(al!=None):
                            t1=isSymmNodes(a.left,b.right);
                        if(ar!=None):
                            t2=isSymmNodes(a.right,b.left);
                        return t1 and t2;
                return False;
    
        if(root==None):return True;
        else:
            return isSymmNodes(root.left,root.right);
    
    # @param root, a tree node
    # @return a boolean
    def isSymmetric(self, root):
        if(root==None):return True;
        else:
            symmPair=[(root.left,root.right)];
            cachePair=[(root.left,root.right)]
            while(len(cachePair)):
                a,b=cachePair.pop(0);
                if(a!=None and b!=None):
                    if(a.left!=None or b.right!=None):
                        symmPair.append((a.left,b.right));
                        cachePair.append((a.left,b.right));
                    if(a.right!=None or b.left!=None):
                        symmPair.append((a.right,b.left));
                        cachePair.append((a.right,b.left));
                if(a!=None and b==None):return False;
                if(b!=None and a==None):return False;
            for (a,b) in symmPair:
                if(a!=None and b==None):return False;
                if(b!=None and a==None):return False;
                if(a!=None and b!=None):
                    if(a.val!=b.val): return False;
            return True;

Log in to reply
 

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