LeetCode 226. 翻转二叉树(C#实现)——二叉树,递归,迭代

一、问题

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

翻转一棵二叉树。

示例：

输入：

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

输出：

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

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

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

二、GitHub实现：https://github.com/JonathanZxxxx/LeetCode/blob/master/InvertTreeClass.cs

　　Blog：https://www.cnblogs.com/zxxxx/

三、思路

　　1、递归：互换左右孩子，对左右孩子进行递归

　　2、迭代：根节点入栈，每次迭代中，移除栈顶元素并互换左右孩子，如果当前节点有左孩子，入栈，为空不做处理，右孩子同理

四、代码实现

 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     }