1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

Input:

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    
    if root.Left == nil && root.Right == nil {
        return root
    }
    
    root.Right, root.Left = invertTree(root.Left), invertTree(root.Right)
    
    return root
    
}