2 recursive and 1 iterative easy-understand Python solutions


  • 7
    G

    An easy-understand iterative solution, checking the symmetry by each layer, top down.

    def isSymmetric(self, root):
        now = []
        if root:
            now.append(root)
        while now:
            vals = []
            for i in now:
                if i:
                    vals.append(i.val)
                else:
                    vals.append(None)
            if list(reversed(vals)) != vals:
                return False
            else:
                now = [j for i in now if i for j in (i.left, i.right)]
        return True
    

    Another simple recursive method, checking whether the original tree = reversed tree with a tuple trick.

    def isSymmetric(self, root):
        def tuple_tree(root):
            return root and (root.val, tuple_tree(root.left), tuple_tree(root.right))
    
        def reverse_tree(root):
            if root:
                root.right, root.left = reverse_tree(root.left), reverse_tree(root.right)
            return root
            
        return tuple_tree(root) == tuple_tree(reverse_tree(root))
    

    My favorite recursive solution, quite clean and efficient.

    def isSymmetric(self, root):
        def sym_tree(L,R):
            if L and R: 
                return L.val == R.val and sym_tree(L.left, R.right) and sym_tree(L.right, R.left)
            else:
                return L == R
        return sym_tree(root, root)

  • 0
    B

    @gene5 Seems excellent. Could you please help me understand the statement [j for i in now if i for j in (i.left, i.right)]? Thanks in advance.


  • 0
    C

    @Billsad

            temp = []
            for i in now:
                if i:
                    temp.append(i.left)
                    temp.append(i.right)
            now = temp
    

Log in to reply
 

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