Iterative solution in Python

  • 0

    The idea is to traverse the left subtree and right subtree synchronously and check their nodes. E.g., we can apply preorder traversal to left subtree and right subtree, but the order of visiting left and right children is opposite.

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution(object):
        def isSymmetric(self, root):
            :type root: TreeNode
            :rtype: bool
            if root == None:    return True
            if root.left==None and root.right==None:    return True
            elif root.left==None or root.right==None:   return False
            stack1, stack2 = [root.left], [root.right]
            while stack1 and stack2:
                node1, node2 = stack1.pop(), stack2.pop()
                if node1==None and node2==None:     continue
                elif node1==None or node2==None:    return False
                    # compare node1 and node2
                    if node1.val != node2.val:  return False
                    # visit left child first for the left sub-tree
                    # visit right child first for the right sub-tree
            return not stack1 and not stack2

Log in to reply

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