Iterative solution in Python


  • 0
    H

    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
                else:
                    # compare node1 and node2
                    if node1.val != node2.val:  return False
                    # visit left child first for the left sub-tree
                    stack1.append(node1.right)
                    stack1.append(node1.left)
                    # visit right child first for the right sub-tree
                    stack2.append(node2.left)
                    stack2.append(node2.right)
                    
            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.