5
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ You present input data both as a list and as a tree. Which one is the actual input form? If it is a list of integers, possibly you could do a recursive analysis just on that list and save the time needed for constructing a tree of linked TreeNode objects? \$\endgroup\$ – CiaPan Apr 1 at 11:33
  • \$\begingroup\$ You 'accepted' my answer, which should confirm my modification is correct and resolves your problem. If so, do you mind to share the scores your modified algorithm achieves? \$\endgroup\$ – CiaPan Apr 1 at 12:46
  • \$\begingroup\$ Where are you submitting these answers to get rankings like this? \$\endgroup\$ – Shawson Apr 1 at 13:16
  • \$\begingroup\$ @Shawson Possibly it's Geeks for geeks? Or may be the LeetCode? \$\endgroup\$ – CiaPan Apr 1 at 17:37
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ As it often happens, optimization needs to fit the actual data characteristics. With BSF one should remember that a full binary tree has \$ 2^d \$ items at the level of depth \$d\$ , so the queue can grow much faster (and larger) than a stack. On the other hand with DSF a stack can grow huge if the tree is degenerated to a list. \$\endgroup\$ – CiaPan Apr 9 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.