剑指Offer面试题19（Java版）：二叉树的镜像
分类：剑指offer（Java版）
题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像
二叉树的结构定义为：
package utils;public class BinaryTreeNode {public int value;public BinaryTreeNode leftNode;public BinaryTreeNode rightNode;public BinaryTreeNode(){}public BinaryTreeNode(int value){this.value = value ;this.leftNode = null;this.rightNode = null;}}树的镜像是一个比较新的概念，我们未必能够一下子相出求树的镜像的方法。为了能够形成直观的印象，我们可以自己画一棵二叉树，然后根据镜子的经验画出它的镜像。如图所示：右边的二叉树就是左边的树的镜像
仔细分析这两棵树的特点，看看能不能总结出求镜像的步骤。这两棵树的根节点相同，但他们的左右两个子节点交换了位置。因此我们不妨先在树中交换根节点的两个子节点，就得到了下面的第二颗树
交换根节点的两个子节点之后，我们注意到值为10，6的结点的子节点仍然保持不变，因此我们还需要交换这两个结点的左右子节点。交换之后的结果分别为第三课树和第四颗树。做完这两次交换之后，我们已经遍历完所有的非叶子结点。此时交换之后的树刚好就是原始树的镜像。
总结上面的过程，我们得出求一棵树的镜像的过程：我们先前序遍历这棵树的每个结点，如果遍历的结点有子节点，就交换它的两个子节点，当交换完所有的非叶子结点的左右子节点之后，我们就得到了镜像。
用Java代码实现：
/** * 题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。 */package swordForOffer;import utils.BinaryTreeNode;/** * @author JInShuangQi * * 2015年8月1日 */public class E19MirrorOfBinaryTree {public void MirrorRecursively(BinaryTreeNode node){if(node == null)return;if(node.leftNode == null && node.rightNode == null)return;BinaryTreeNode temp = node.leftNode;node.leftNode = node.rightNode;node.rightNode = temp;if(node.leftNode != null)MirrorRecursively(node.leftNode);if(node.rightNode != null)MirrorRecursively(node.rightNode);}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇剑指Offer面试题18（Java版）：树的子结构下一篇剑指Offer面试题20（Java版）：顺时针打印矩阵
顶1踩0
，如果前世五百次眸回，才换来今生的擦肩而过。
