Ggthjy

I tried to solve a symmetric tree problem

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1

   / 

  2   2

 /  / 

3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1

   / 

  2   2

      

   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

My solution with recursion

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None



class Solution(object):

    def isSymmetric(self, root):

        if not root: return True #None is symmetic 

        return self.isMirror(root.left, root.right)





    def isMirror(self, l, r):

        if not l and not r: return True #base case 1

        if not l or not r: return False #base case 2

        if l.val != r.val: return False #base case 3

        #recur case 

        left = self.isMirror(l.left, r.right)

        right = self.isMirror(l.right, r.left)

        return left and right

I assumed it as a decent solution to this problem but get a low score

Runtime: 32 ms, faster than 24.42% of Python online submissions for Symmetric Tree.
Memory Usage: 12.2 MB, less than 5.08% of Python online submissions for Symmetric Tree.

How could improve the my solution?

Possibly the most obvious part is here

    left = self.isMirror(l.left, r.right)

    right = self.isMirror(l.right, r.left)

    return left and right

there's no need to perform the second test if the first one returns False:

    if not self.isMirror(l.left, r.right): return False

    if not self.isMirror(l.right, r.left): return False



    return True

Appart from the optimization provided by @CiaPan, you could try using an inner function to reduce the need for attributes lookups and accelerate symbols resolution speed:

class Solution(object):

    def isSymmetric(self, root):

        if root is None:

            return True



        def isMirror(left, right):

            if left is None and right is None:

                return True

            elif left is None or right is None:

                return False

            elif left.val != right.val:

                return False

            else:

                return isMirror(left.left, right.right) and isMirror(left.right, right.left)



        return isMirror(root.left, root.right)

Alternatively, you could try the iterative approach which is usually implemented using a deque to perform a breadth first search:

from collections import deque





class Solution(object):

    def isSymmetric(self, root):

        if root is None:

            return True



        rights = deque([root.right])

        lefts = deque([root.left])

        while lefts:

            left = lefts.popleft()

            right = right.popleft()

            if left is None and right is None:

                pass

            elif left is None or right is None:

                return False

            elif left.val != right.val:

                return False

            else:

                lefts.append(left.left)

                lefts.append(left.right)

                rights.append(right.right)

                rights.append(right.left)



        return True