1Input:
2
3     4
4   /   \
5  2     7
6 / \   / \
71   3 6   9
8Output:
9
10     4
11   /   \
12  7     2
13 / \   / \
149   6 3   1

1# Invert a binary tree.
2#
3# Example:
4#
5# Input:
6#
7#      4
8#    /   \
9#   2     7
10#  / \   / \
11# 1   3 6   9
12# Output:
13#
14#      4
15#    /   \
16#   7     2
17#  / \   / \
18# 9   6 3   1
19
20# Definition for a binary tree node.
21# class TreeNode:
22#     def __init__(self, x):
23#         self.val = x
24#         self.left = None
25#         self.right = None
26
27class Solution:
28    def invertTree(self, root):
29        """
30        :type root: TreeNode
31        :rtype: TreeNode
32        """
33        if not root:
34            return
35        root.left,root.right = root.right,root.left
36        self.invertTree(root.left)
37        self.invertTree(root.right)
38        return root
39