Symmetric Tree (Iterative)

Question Description

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

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Solution

The recursive way here is very simple, so I just illustrate the iterative way here. Here I maintain a left stack and a right stack to compare all the left subtrees and right subtrees. In every iteration of the loop, I pop two last elements from these two stacks to compare if they are equal.

In this case, when I push new elements in the stack, I should make the comparison order correct by pushing right and left in the right stack and pushing left and right in the left stack at the same time. Then we will compare l.left to r.right and compare l.right to r.left.

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root: return True
        lstk, rstk = [root.left], [root.right]
        while len(lstk) > 0 and len(rstk) > 0:
            l, r = lstk.pop(), rstk.pop()
            if not l and not r:
                pass
            elif l and r:
                if l.val != r.val:
                    return False
                rstk.append(r.right)
                rstk.append(r.left)
                lstk.append(l.left)
                lstk.append(l.right)
            else:
                return False
        return True