翻转一棵二叉树。

示例：

输入：

     4
   /     2     7
 / \   / 1   3 6   9

输出：

     4
   /     7     2
 / \   / 9   6 3   1

备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：

    谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

 1     public class InvertTreeClass
 2     {
 3         /// <summary>
 4         /// 递归
 5         /// </summary>
 6         /// <param name="root"></param>
 7         /// <returns></returns>
 8         public TreeNode InvertTree(TreeNode root)
 9         {
10             if (root == null)
11             {
12                 return null;
13             }
14             var left = InvertTree(root.right);
15             var right = InvertTree(root.left);
16             root.left = left;
17             root.right = right;
18             return root;
19         }
20 
21         /// <summary>
22         /// 迭代
23         /// </summary>
24         /// <param name="root"></param>
25         /// <returns></returns>
26         public TreeNode InvertTree2(TreeNode root)
27         {
28             if (root == null) return null;
29             var stack = new Stack<TreeNode>();
30             stack.Push(root);
31             while (stack.Any())
32             {
33                 var pop = stack.Pop();
34                 var temp = pop.left;
35                 pop.left = pop.right;
36                 pop.right = temp;
37                 if (pop.left != null) stack.Push(pop.left);
38                 if (pop.right != null) stack.Push(pop.right);
39             }
40             return root;
41         }
42     }
43 
44     public class TreeNode
45     {
46         public int val;
47         public TreeNode left;
48         public TreeNode right;
49         public TreeNode(int x) { val = x; }
50     }