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.left20 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.left10 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}
总结
这题没什么难度，但解法比较多，主要是因为二叉树的遍历方式比较多，如果每一种方式递归和非递归都写的话就更多了。
长按上图，识别图中二维码之后即可关注。
如果觉得有用就点个"赞"吧
本文分享自微信公众号 - 数据结构和算法（sjjghsf）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
