二叉树的镜像：将一个二叉树的左右子树，调换位置。即下图的形式：
递归的思想是：
从根节点的左右子树进行交换，然后以根节点的左子树为根节点，而后以根节点的右结点为根节点，进行左右子树交换。遇到空节点或叶节点直接返回。下面求二叉树镜像的函数代码实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
template<class T> void MirroTree(TreeNode<T> * root) { if (root == NULL) return; if (root->_left == NULL && root->_right == NULL) return; else { TreeNode<T>* temp = root->_left; root->_left = root->_right; root->_right = temp; } MirroTree(root->_left); MirroTree(root->_right); } |
非递归实现思想：
利用stack栈的FILO，即先进后出原则，将根节点先行压入栈中，然后进入栈同时取栈顶结点并pop栈，然后交换左右子树的结点，若根节点的左右子树不为空，即压入栈中，直到栈为空则停止。
下面是非递归实现代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
template<class T> void MirroTree_NoR(TreeNode<T>* root) { stack<TreeNode<T>*> s; s.push(root); while (s.size()) { TreeNode<T>* Top = s.top(); if (Top->_left != NULL || Top->_right != NULL) { TreeNode<T>* temp = Top->_left; Top->_left = Top->_right; Top->_right = temp; } if (Top->_left != NULL) s.push(Top->_left); if (Top->_right != NULL) s.push(Top->_right); } } |
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://blog.csdn.net/he_shuai20/article/details/72670136
