Symmetric Tree

Problem: Symmetric Tree

The general idea is first compare leftmost path of the tree and rightmost path of the tree, then compare two closer path. We can use a depth-first search based on stack to implement this solution. We can first push left child and right child of the root into the stack then check whether they are the same or not, then push their children correspondingly into the stack and do the same thing. By word "correspondingly", we need to note that left subtree of left child of root corresponds to right subtree of the right child.

Code in Python:

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        stack = [root.left, root.right]
        while stack:
            a = stack.pop()
            b = stack.pop()
            if not a and not b:
                continue
            if (not a and b) or (a and not b):
                return False
            if a.val == b.val:
                stack.extend([a.left, b.right, a.right, b.left])
            else:
                return False
        return True