剑指Offer面试题19（Java版）：二叉树的镜像

傷城~ 2022-07-16 04:37 142阅读 0赞

题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像

二叉树的结构定义为：

**\[java\]**  [view plain][]   [copy][view plain]

1.  **package** utils;  
2.    
3.  **public** **class** BinaryTreeNode \{  
4.      **public** **int** value;  
5.      **public** BinaryTreeNode leftNode;  
6.      **public** BinaryTreeNode rightNode;  
7.        
8.      **public** BinaryTreeNode()\{  
9.            
10.     \}  
11.     **public** BinaryTreeNode(**int** value)\{  
12.         **this**.value = value ;  
13.         **this**.leftNode = **null**;  
14.         **this**.rightNode = **null**;  
15.     \}  
16.       
17. \}

树的镜像是一个比较新的概念，我们未必能够一下子相出求树的镜像的方法。为了能够形成直观的印象，我们可以自己画一棵二叉树，然后根据镜子的经验画出它的镜像。  
如图所示：右边的二叉树就是左边的树的镜像

![Center][]

仔细分析这两棵树的特点，看看能不能总结出求镜像的步骤。这两棵树的根节点相同，但他们的左右两个子节点交换了位置。因此我们不妨先在树中交换根节点的两个子节点，就得到了下面的第二颗树

![Center 1][]

交换根节点的两个子节点之后，我们注意到值为10，6的结点的子节点仍然保持不变，因此我们还需要交换这两个结点的左右子节点。交换之后的结果分别为第三课树和第四颗树。做完这两次交换之后，我们已经遍历完所有的非叶子结点。此时交换之后的树刚好就是原始树的镜像。

总结上面的过程，我们得出求一棵树的镜像的过程：我们先前序遍历这棵树的每个结点，如果遍历的结点有子节点，就交换它的两个子节点，当交换完所有的非叶子结点的左右子节点之后，我们就得到了镜像。

用Java代码实现：

**\[java\]**  [view plain][]   [copy][view plain]

1.  /\*\* 
2.   \* 题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。 
3.   \*/  
4.  **package** swordForOffer;  
5.    
6.  **import** utils.BinaryTreeNode;  
7.    
8.  /\*\* 
9.   \* @author JInShuangQi 
10.  \* 
11.  \* 2015年8月1日 
12.  \*/  
13. **public** **class** E19MirrorOfBinaryTree \{  
14.     **public** **void** MirrorRecursively(BinaryTreeNode node)\{  
15.         **if**(node == **null**)  
16.             **return**;  
17.         **if**(node.leftNode == **null** && node.rightNode == **null**)  
18.             **return**;  
19.         BinaryTreeNode temp = node.leftNode;  
20.         node.leftNode = node.rightNode;  
21.         node.rightNode = temp;  
22.         **if**(node.leftNode != **null**)  
23.             MirrorRecursively(node.leftNode);  
24.         **if**(node.rightNode != **null**)  
25.             MirrorRecursively(node.rightNode);  
26.     \}  
27. \}

[view plain]: http://blog.csdn.net/jsqfengbao/article/details/47208709#
[Center]: /images/20220716/717adac8ef4449cc9ff3a00ed3c6d27d.png
[Center 1]: /images/20220716/abade63dfdbf4a68802fc4ab6c0bbf8b.png