剑指offer18：操作给定的二叉树，将其变换为源二叉树的镜像。

1 题目描述

　　操作给定的二叉树，将其变换为源二叉树的镜像。

2 输入描述:

二叉树的镜像定义：源二叉树

    	    8

    	   /  \

    	  6   10

    	 / \  / \

    	5  7 9 11

    	镜像二叉树

    	    8

    	   /  \

    	  10   6

    	 / \  / \

    	11 9 7  5

3 思路和方法

　　（1）递归思想，先交换根节点的左右子树的位置，然后向下递归，把左右子树的根节点作为下次循环的根节点。

　　（2）非递归：所以我们可以采用前序遍历的方法进行操作，每当遇到一个结点的时候，首先判断其是否有左右孩子（有其中之一即可），如果有的话，就交换其左右孩子，然后继续遍历其左右子树，只要不为空就继续交换其左右孩子节点（在交换具有孩子结点的结点的时候，其孩子结点也一并被交换了）。

4. C++核心代码

4.1 循环实现二叉树的镜像，利用栈的“后进先出”特性打印

 /*

 struct TreeNode {

     int val;

     struct TreeNode *left;

     struct TreeNode *right;

     TreeNode(int x) :

             val(x), left(NULL), right(NULL) {

     }

 };*/

 class Solution {

 public:

     void Mirror(TreeNode *root) {

         if (root == NULL)

             return;

         stack<TreeNode*> stackTreeNode;

         stackTreeNode.push(root);

         while (stackTreeNode.size() > )

         {

             TreeNode *parent = stackTreeNode.top();

             stackTreeNode.pop();

             TreeNode *Temp = parent->left;

             parent->left = parent->right;

             parent->right = Temp;

             if (parent->left)

                 stackTreeNode.push(parent->left);

             if (parent->right)

                 stackTreeNode.push(parent->right);

         }

     }

 };

4.2 递归实现二叉树的镜像，按照先序遍历，如果遇到空的节点或者叶子节点就返回，否则交换两个子树后再改变左右子树

 /*

 struct TreeNode {

     int val;

     struct TreeNode *left;

     struct TreeNode *right;

     TreeNode(int x) :

             val(x), left(NULL), right(NULL) {

     }

 };*/

 class Solution {

 public:

     void Mirror(TreeNode *pRroot) {

         if (pRroot == NULL || (pRroot->left == NULL && pRroot->right == NULL))

             return;

         TreeNode * tmp = pRroot->left;

         pRroot->left = pRroot->right;

         pRroot->right = tmp;

         if (pRroot->left)

             Mirror(pRroot->left);

         if (pRroot->right)

             Mirror(pRroot->right);

     }

 };

5. 完整代码

 #include<iostream>

 #include<stack>

 using namespace std;

 struct BinaryTreeNode

 {

     int data;

     BinaryTreeNode* leftchild;

     BinaryTreeNode* rightchild;

     BinaryTreeNode(int t)

     {

         data = t;

         leftchild = NULL;

         rightchild = NULL;

     }

 };

 void PreorderTravel(BinaryTreeNode* root)

 {

     if (root == NULL)

     {

         return;

     }

     cout << root->data << "    ";

     PreorderTravel(root->leftchild);

     PreorderTravel(root->rightchild);

 }

 //递归实现二叉树的镜像，按照先序遍历，如果遇到空的节点或者叶子节点就返回，否则交换两个子树后再改变左右子树

 void MirrorBinaryTree1(BinaryTreeNode* root)

 {

     if (root == NULL || (root->leftchild == NULL && root->rightchild == NULL))

     {

         return;

     }

     BinaryTreeNode * tmp = root->leftchild;

     root->leftchild = root->rightchild;

     root->rightchild = tmp;

     if (root->leftchild)

     {

         MirrorBinaryTree1(root->leftchild);

     }

     if (root->rightchild)

     {

         MirrorBinaryTree1(root->rightchild);

     }

 }

 //循环实现二叉树的镜像，利用栈的“后进先出”特性打印

 void MirrorBinaryTree2(BinaryTreeNode* root)

 {

     if (root == NULL)

     {

         return;

     }

     stack<BinaryTreeNode*> stackTreeNode;

     stackTreeNode.push(root);

     while (stackTreeNode.size() > )

     {

         BinaryTreeNode *parent = stackTreeNode.top();

         stackTreeNode.pop();

         BinaryTreeNode *Temp = parent->leftchild;

         parent->leftchild = parent->rightchild;

         parent->rightchild = Temp;

         if (parent->leftchild)

         {

             stackTreeNode.push(parent->leftchild);

         }

         if (parent->rightchild)

         {

             stackTreeNode.push(parent->rightchild);

         }

     }

 }

 // ====================测试代码====================

 // 测试完全二叉树：除了叶子节点，其他节点都有两个子节点

 //            8

 //      6        10

 //   5  7      9  11

 BinaryTreeNode* root;

 void Test1()

 {

     root = new BinaryTreeNode();

     root->leftchild = new BinaryTreeNode();

     root->rightchild = new BinaryTreeNode();

     BinaryTreeNode* tmp = root->leftchild;

     tmp->leftchild = new BinaryTreeNode();

     tmp->rightchild = new BinaryTreeNode();

     tmp = root->rightchild;

     tmp->leftchild = new BinaryTreeNode();

     tmp->rightchild = new BinaryTreeNode();

     cout << "Test1:测试完全二叉树,除了叶子节点，其他节点都有两个子节点" << endl;

     cout << "原二叉树的先序遍历" << endl;

     PreorderTravel(root);

     cout << endl;

     MirrorBinaryTree1(root);

     cout << "二叉树镜像后的先序遍历" << endl;

     PreorderTravel(root);

     cout << endl;

     /*MirrorBinaryTree2(root);

     cout << "二叉树镜像后的先序遍历" << endl;

     PreorderTravel(root);

     cout << endl;*/

 }

 // 测试二叉树：出叶子结点之外，左右的结点都有且只有一个左子结点

 //            8

 //          7

 //        6

 //      5

 //

 void Test2()

 {

     root = new BinaryTreeNode();

     root->leftchild = new BinaryTreeNode();

     root->rightchild = NULL;

     BinaryTreeNode* tmp = root->leftchild;

     tmp->leftchild = new BinaryTreeNode();

     tmp->rightchild = NULL;

     tmp = tmp->leftchild;

     tmp->leftchild = new BinaryTreeNode();

     tmp->rightchild = NULL;

     tmp = tmp->leftchild;

     tmp->leftchild = new BinaryTreeNode();

     tmp->rightchild = NULL;

     cout << "Test2: 测试二叉树,出叶子结点之外，左右的结点都有且只有一个左子结点" << endl;

     cout << "原二叉树的先序遍历" << endl;

     PreorderTravel(root);

     cout << endl;

     MirrorBinaryTree1(root);

     cout << "二叉树镜像后的先序遍历" << endl;

     PreorderTravel(root);

     cout << endl;

     /*MirrorBinaryTree2(root);

     cout << "二叉树镜像后的先序遍历" << endl;

     PreorderTravel(root);

     cout << endl;*/

 }

 // 测试二叉树：出叶子结点之外，左右的结点都有且只有一个右子结点

 //            8

 //             7

 //              6

 //               5

 //                4

 void Test3()

 {

     root = new BinaryTreeNode();

     root->leftchild = NULL;

     root->rightchild = new BinaryTreeNode();

     BinaryTreeNode* tmp = root->rightchild;

     tmp->leftchild = NULL;

     tmp->rightchild = new BinaryTreeNode();

     tmp = tmp->rightchild;

     tmp->leftchild = NULL;

     tmp->rightchild = new BinaryTreeNode();

     tmp = tmp->rightchild;

     tmp->leftchild = NULL;

     tmp->rightchild = new BinaryTreeNode();

     cout << "Test3:测试二叉树出叶子结点之外，左右的结点都有且只有一个右子结点" << endl;

     cout << "原二叉树的先序遍历" << endl;

     PreorderTravel(root);

     cout << endl;

     MirrorBinaryTree1(root);

     cout << "二叉树镜像后的先序遍历" << endl;

     PreorderTravel(root);

     cout << endl;

     /*MirrorBinaryTree2(root);

     cout << "二叉树镜像后的先序遍历" << endl;

     PreorderTravel(root);

     cout << endl;*/

 }

 // 测试空二叉树：根结点为空指针

 void Test4()

 {

     root = NULL;

     cout << "Test4:测试空二叉树,根结点为空指针" << endl;

     cout << "原二叉树的先序遍历" << endl;

     PreorderTravel(root);

     cout << endl;

     MirrorBinaryTree1(root);

     cout << "二叉树镜像后的先序遍历" << endl;

     PreorderTravel(root);

     cout << endl;

     /*MirrorBinaryTree2(root);

     cout << "二叉树镜像后的先序遍历" << endl;

     PreorderTravel(root);

     cout << endl;*/

 }

 // 测试只有一个结点的二叉树

 void Test5()

 {

     root = new BinaryTreeNode();

     root->leftchild = NULL;

     root->rightchild = NULL;

     cout << "Test5:测试只有一个结点8的二叉树" << endl;

     cout << "原二叉树的先序遍历" << endl;

     PreorderTravel(root);

     cout << endl;

     MirrorBinaryTree1(root);

     cout << "二叉树镜像后的先序遍历" << endl;

     PreorderTravel(root);

     cout << endl;

     /*MirrorBinaryTree2(root);

     cout << "二叉树镜像后的先序遍历" << endl;

     PreorderTravel(root);

     cout << endl;*/

 }

 int main()

 {

     Test1();

     Test2();

     Test3();

     Test4();

     Test5();

     system("pause");

     return ;

 }

参考资料

https://blog.csdn.net/yanxiaolx/article/details/52019871

巴特西