求解二叉树镜像
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了求解二叉树镜像，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4413字，纯文字阅读大概需要7分钟。
内容图文
一，问题介绍
求解一棵二叉树的镜像。所谓镜像，就是从二叉树的根到叶结点的每一层，将所有的非叶子结点的孩子进行交换。
比如说，下面两棵二叉树互为镜像：
二，算法分析
1
/**
2
* 递归求解二叉树的镜像
3
*
@param
root
4
*/
5
public
void mirrorRecursively(BinaryNode<T> root){
6//base condition 7if(root == null || (root.left == null && root.right == null))
8return;
910//swap nodes11 BinaryNode<T> tmp;
12 tmp = root.left;
13 root.left = root.right;
14 root.right = tmp;
1516//recursively call17if(root.left != null)
18 mirrorRecursively(root.left);
19if(root.right != null)
20 mirrorRecursively(root.right);
21 }
从根结点开始，先交换根结点的左右孩子， 然后再依次交换根结点的左右孩子的孩子......
时间复杂度分析：由于每个结点都会遍历一次，故时间复杂度为O(N)，也可以列出递归表达式如下：
递归表达式：T(N)=2T(N/2)+O(1). 由17行到20行的两个if语句，可知将问题规模为N分解成了两个规模为N/2的两个子问题；附加的处理规模为O(1)
解得T(N)=O(N)
尾递归转化为循环：
1
/**
2
* 循环实现 求解二叉树的镜像
3
*
@param
root
4
*/
5
public
void mirrorLoop(BinaryNode<T> root){
6if(root == null || (root.left == null && root.right == null))
7return;
8 9 swap(root.left, root.right, root);//根的左右孩子的交换
1011//处理根的左子树的交换12 BinaryNode<T> currentNode = root;
13while(currentNode.left != null)
14 {
15 currentNode = currentNode.left;
16 swap(currentNode.left, currentNode.right, currentNode);
17 }
1819//处理根的右子树的交换20 currentNode = root;
21while(currentNode.right != null)
22 {
23 currentNode = currentNode.right;
24 swap(currentNode.left, currentNode.right, currentNode);
25 }
26 }
三，完整代码实现
递归实现和非递归实现。由于该递归是一个尾递归，故非递归实现也很简单。
1
public
class BinaryTree_Mirror<T extends Comparable<? super T>> {
2 3privatestaticclass BinaryNode<T>{
4 T element;
5 BinaryNode<T> left;
6 BinaryNode<T> right;
7 8public BinaryNode(T element) {
9this.element = element;
10 left = right = null;
11 }
12 13 @Override
14public String toString() {
15return element.toString();
16 }
17 }
18 19private BinaryNode<T> root;
20 21/** 22 * 向二叉树中插入一个元素
23 * @param element
24*/ 25publicvoid insert(T element){
26 root = insert(root, element);
27 }
28private BinaryNode<T> insert(BinaryNode<T> root, T element){
29if(root == null)
30returnnew BinaryNode<T>(element);
31int r = (int)(2*Math.random());
32//随机地将元素插入到左子树 或者 右子树中 33if(r==0)
34 root.left = insert(root.left, element);
35else 36 root.right = insert(root.right, element);
37return root;
38 }
39 40publicvoid inOrder(BinaryNode<T> root){
41//base condition 42if(root == null)
43return;
44 45 inOrder(root.left);
46 System.out.print(root + " ");//visit node 47 inOrder(root.right);
48 }
49 50 51/** 52 * 递归求解二叉树的镜像
53 * @param root
54*/ 55publicvoid mirrorRecursively(BinaryNode<T> root){
56//base condition 57if(root == null || (root.left == null && root.right == null))
58return;
59 60//swap nodes 61 BinaryNode<T> tmp;
62 tmp = root.left;
63 root.left = root.right;
64 root.right = tmp;
65 66//recursively call 67if(root.left != null)
68 mirrorRecursively(root.left);
69if(root.right != null)
70 mirrorRecursively(root.right);
71 }
72 73/** 74 * 循环实现 求解二叉树的镜像
75 * @param root
76*/ 77publicvoid mirrorLoop(BinaryNode<T> root){
78if(root == null || (root.left == null && root.right == null))
79return;
80 81 swap(root.left, root.right, root);
82 83 BinaryNode<T> currentNode = root;
84while(currentNode.left != null)
85 {
86 currentNode = currentNode.left;
87 swap(currentNode.left, currentNode.right, currentNode);
88 }
89 90 currentNode = root;
91while(currentNode.right != null)
92 {
93 currentNode = currentNode.right;
94 swap(currentNode.left, currentNode.right, currentNode);
95 }
96 }
97 98/** 99 * 交换currentNode的左右孩子结点
100 * @param left
101 * @param right
102 * @param currentNode
103*/104privatevoid swap(BinaryNode<T> left, BinaryNode<T> right, BinaryNode<T> currentNode){
105 BinaryNode<T> tmpNode;
106 tmpNode = currentNode.left;
107 currentNode.left = currentNode.right;
108 currentNode.right = tmpNode;
109 }
110111112publicstaticvoid main(String[] args) {
113 BinaryTree_Mirror<Integer> tree1 = new BinaryTree_Mirror<>();
114 BinaryTree_Mirror<Integer> tree2 = new BinaryTree_Mirror<>();
115116int[] ele = C2_2_8.algorithm1(4);
117for (int i = 0; i < ele.length; i++) {
118 tree1.insert(ele[i]);
119 tree2.insert(ele[i]);
120 }
121122 tree1.mirrorLoop(tree1.root);
123 tree2.mirrorRecursively(tree2.root);
124125 tree1.inOrder(tree1.root);
126 System.out.println();
127 tree2.inOrder(tree2.root);
128 }
129 }
原文：http://www.cnblogs.com/hapjin/p/5553846.html
内容总结
以上是互联网集市为您收集整理的求解二叉树镜像全部内容，希望文章能够帮你解决求解二叉树镜像所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】