# O(n) time | O(d) space
def invertBinaryTree(tree):
    if tree is None:
         return 0
    (tree.left, tree.right) = (tree.right, tree.left)
    if tree.left:
        invertBinaryTree(tree.left)
    if tree.right:
        invertBinaryTree(tree.right)

# O(n) time | O(n) space
def invertBinaryTree(tree):
    queue = [tree]
    while len(queue):
        current = queue.pop(0)
        if current is None:
            continue
        tree.left, tree.right = tree.right, tree.left
        queue.append(current.left)
        queue.append(current.right)

def isSameTree(self, p, q):
    if p or q is None:
        return False
    if p and q is None:
        return True
    if p != q:
        return False
    self.isSameTree(p.left, q.left)
    self.isSameTree(p.right, q.right)

def isSymmetric(self, root):
    if root is None:
        return 0
    return self._isSymmetric(root.left, root.right)

def _isSymmetric(self, left, root):
    if left or right is None:
        return False
    if left and right is None:
        return True
    if left.val == right.val:
        isSameChildNode1 = self._isSymmetric(left.left, right.right)
        isSameChildNode2 = self._isSymmetric(left.right, right.left)
    else:
        return False