434，剑指 Offer-二叉树的镜像
The more you know who you are and what you want, the less you let things upset you.
你越了解自己以及自己想要的东西，你就越不会被外界困扰。
问题描述
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出：
4
/ \
7 2
/ \ / \
9 6 3 1
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
限制：
0 <= 节点个数 <= 1000
BFS解决
之前讲373，数据结构-6,树的时候，提到过二叉树的广度优先搜索，就是一层一层的访问，像下面这样
二叉树的BFS代码如下
1public static void treeBFS(TreeNode root) {
2 //如果为空直接返回
3 if (root == null)
4 return;
5 //队列
6 Queue<TreeNode> queue = new LinkedList<>();
7 //首先把根节点加入到队列中
8 queue.add(root);
9 //如果队列不为空就继续循环
10 while (!queue.isEmpty()) {
11 //poll方法相当于移除队列头部的元素
12 TreeNode node = queue.poll();
13 //打印当前节点
14 System.out.println(node.val);
15 //如果当前节点的左子树不为空，就把左子树
16 //节点加入到队列中
17 if (node.left != null)
18 queue.add(node.left);
19 //如果当前节点的右子树不为空，就把右子树
20 //节点加入到队列中
21 if (node.right != null)
22 queue.add(node.right);
23 }
24}
这题要求的是输出二叉树的镜像，就是每一个节点的左右子节点进行交换，随便画个二叉树看一下
我们需要遍历每一个节点，然后交换他的两个子节点，一直循环下去，直到所有的节点都遍历完为止，代码如下
1public TreeNode mirrorTree(TreeNode root) {
2 //如果为空直接返回
3 if (root == null)
4 return null;
5 //队列
6 final Queue<TreeNode> queue = new LinkedList<>();
7 //首先把根节点加入到队列中
8 queue.add(root);
9 while (!queue.isEmpty()) {
10 //poll方法相当于移除队列头部的元素
11 TreeNode node = queue.poll();
12 //交换node节点的两个子节点
13 TreeNode left = node.left;
14 node.left = node.right;
15 node.right = left;
16 //如果当前节点的左子树不为空，就把左子树
17 //节点加入到队列中
18 if (node.left != null) {
19 queue.add(node.left);
20 }
21 //如果当前节点的右子树不为空，就把右子树
22 //节点加入到队列中
23 if (node.right != null) {
24 queue.add(node.right);
25 }
26 }
27 return root;
28}
DFS解决
无论是BFS还是DFS都会访问到每一个节点，访问每个节点的时候交换他的左右子节点，直到所有的节点都访问完为止，代码如下
1public TreeNode mirrorTree(TreeNode root) {//DFS
2 //如果为空直接返回
3 if (root == null)
4 return null;
5 //栈
6 Stack<TreeNode> stack = new Stack<>();
7 //根节点压栈
8 stack.push(root);
9 //如果栈不为空就继续循环
10 while (!stack.empty()) {
11 //出栈
12 TreeNode node = stack.pop();
13 //子节点交换
14 TreeNode temp = node.left;
15 node.left = node.right;
16 node.right = temp;
17 //左子节点不为空入栈
18 if (node.left != null)
19 stack.push(node.left);
20 //右子节点不为空入栈
21 if (node.right != null)
22 stack.push(node.right);
23 }
24 return root;
25}
中序遍历解决
这题其实解法比较多，只要访问他的每一个节点，然后交换子节点即可，我们知道二叉树不光有BFS和DFS访问顺序，而且还有前序遍历，中序遍历和后续遍历等，不管哪种访问方式，只要能把所有节点都能访问一遍然后交换子节点就能解决，我们这里就以中序遍历来看下，前序和后序就不在看了。在373，数据结构-6,树中，提到二叉树中序遍历的非递归写法如下
1public static void inOrderTraversal(TreeNode tree) {
2 Stack<TreeNode> stack = new Stack<>();
3 while (tree != null || !stack.isEmpty()) {
4 while (tree != null) {
5 stack.push(tree);
6 tree = tree.left;
7 }
8 if (!stack.isEmpty()) {
9 tree = stack.pop();
10 System.out.println(tree.val);
11 tree = tree.right;
12 }
13 }
14}
我们来对他改造一下，就是在访问每个节点的时候交换，代码如下
1public static TreeNode mirrorTree(TreeNode root) {
2 //如果为空直接返回
3 if (root == null)
4 return null;
5 Stack<TreeNode> stack = new Stack<>();
6 TreeNode node = root;
7 while (node != null || !stack.isEmpty()) {
8 while (node != null) {
9 stack.push(node);
10 node = node.left;
11 }
12 if (!stack.isEmpty()) {
13 node = stack.pop();
14 //子节点交换
15 TreeNode temp = node.left;
16 node.left = node.right;
17 node.right = temp;
18 //注意这里以前是node.right，因为上面已经交换了
19 //，所以这里要改为node.left
20 node = node.left;
21 }
22 }
23 return root;
24}
递归方式解决
二叉树中序遍历的递归代码如下
1public void inOrderTraversal(TreeNode node) {
2 if (node == null)
3 return;
4 inOrderTraversal(node.left);
5 System.out.println(node.val);
6 inOrderTraversal(node.right);
7}
上面说了，只要能访问二叉树的每一个节点，然后交换左右子节点就行了，这里就以二叉树中序遍历递归的方式来看下
1public TreeNode mirrorTree(TreeNode root) {
2 if (root == null)
3 return null;
4 mirrorTree(root.left);
5 //子节点交换
6 TreeNode temp = root.left;
7 root.left = root.right;
8 root.right = temp;
9 //上面交换过了，这里root.right要变成root.left
10 mirrorTree(root.left);
11 return root;
12}
再来看一个后续遍历的
1public TreeNode mirrorTree(TreeNode root) {
2 if (root == null)
3 return null;
4 TreeNode left = mirrorTree(root.left);
5 TreeNode right = mirrorTree(root.right);
6 root.left = right;
7 root.right = left;
8 return root;
9}
总结
这题没什么难度，但解法比较多，主要是因为二叉树的遍历方式比较多，如果每一种方式递归和非递归都写的话就更多了。
长按上图，识别图中二维码之后即可关注。
如果觉得有用就点个"赞"吧