"""Leetcode 226. Invert Binary Tree
Easy

URL: https://leetcode.com/problems/invert-binary-tree/

Invert a binary tree.

Example:

Input:

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

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

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


class SolutionRecur(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode

        Time complexity: O(n).
        Space complexity: O(n).
        """
        if not root:
            return None

        left = self.invertTree(root.left)
        right = self.invertTree(root.right)

        root.left = right
        root.right = left
        return root


def main():
    root = TreeNode(4)
    root.left = TreeNode(2)
    root.right = TreeNode(7)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(3)
    root.right.left = TreeNode(6)
    root.right.right = TreeNode(9)

    root = SolutionRecur().invertTree(root)
    print root.val              # Should be 4.
    print root.left.val         # Should be 7.
    print root.right.val        # Should be 2.
    print root.left.left.val    # Should be 9.
    print root.left.right.val   # Should be 6.
    print root.right.left.val   # Should be 3.
    print root.right.right.val  # Should be 1.


if __name__ == '__main__':
    main()


@@ -659,16 +659,77 @@
 n None%0A%0A
+        # Recursively invert left subtree and right subtree.%0A
         
@@ -819,51 +819,797 @@
     
-root.left = right%0A        root.right = left
+# Invert tree by interchanging left and right trees.%0A        root.left = right%0A        root.right = left%0A        return root%0A%0A%0Aclass SolutionIter(object):%0A    def invertTree(self, root):%0A        %22%22%22%0A        :type root: TreeNode%0A        :rtype: TreeNode%0A%0A        Time complexity: O(n).%0A        Space complexity: O(n).%0A        %22%22%22%0A        if not root:%0A            return root%0A%0A        # Apply BFS w/ queue to iteratively visit and invert tree.%0A        queue = %5Broot%5D%0A        while queue:%0A            visit = queue.pop()%0A            # Invert tree by interchanging left and right trees.%0A            visit.left, visit.right = visit.right, visit.left%0A            if visit.left:%0A                queue.insert(0, visit.left)%0A            if visit.right:%0A                queue.insert(0, visit.right)%0A
 %0A   
@@ -1855,24 +1855,26 @@
 Node(9)%0A%0A   
+ #
  root = Solu
@@ -1902,16 +1902,59 @@
 e(root)%0A
+    root = SolutionIter().invertTree(root)%0A
     prin

Complete invert binary tree by iterative alg