LeetCode: Invert Binary Tree

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

In the above tree, the output will be a list = [4,7,2,9,6,3,1]

# 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 invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        #print 'root val: ', root.val
        mirrorList = []
        if not root:
            return mirrorList
            
        # do a BFS. Use a Queue - FIFO to traverse the original list
        from collections import deque
        Q = deque()
        Q.append(root)
        mirrorList.append(root.val)
        while len(Q) != 0:
            node = Q.popleft()
            
            #//////////////////////////////////////
            # now turn the direction first
            # This is the most important step
            # to mirror the tree
            #//////////////////////////////////////
            temp = node.left
            node.left = node.right
            node.right = temp
            
            
            # then append the turned node to the mirrored List and the Q
            if node.left is not None:
                mirrorList.append(node.left.val)
                Q.append(node.left)
            else:
                mirrorList.append(None)
                
            if node.right is not None:
                mirrorList.append(node.right.val)
                Q.append(node.right)
            else:
                mirrorList.append(None)
                
        
        #Trim the null's from the end, since mirrorList can get some extra nulls at it's end
        for item in mirrorList[::-1]:
            if item == None:
                mirrorList.pop()
            else:
                break
        return mirrorList