18.二叉树的镜像.md

18.二叉树的镜像

题目描述

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

• 输入描述：

  二叉树的镜像定义：源二叉树 
      	    8
      	   /  \
      	  6   10
      	 / \  / \
      	5  7 9 11
      	镜像二叉树
      	    8
      	   /  \
      	  10   6
      	 / \  / \
      	11 9 7  5
  

  ​

解题思路

• 递归的思想，从上往下依次把左右子树交换不就行了？So easy !（前序遍历）

• 迭代的思想，需要借助队列或者栈：

  • 队列方式，先将根结点压入队列，然后当队列不为空时，弹出队首结点，交换其左右子结点，然后将左右子结点压入队列（层次遍历）；
  • 栈的方式，借助于栈的方式和上面的第二种队列方式差不多，先将根结点入栈，然后当栈不为空时，弹出栈顶结点，交换其左右子结点，然后将左右子结点入栈（前序遍历）。

• 这个题目实际上有点像二叉树的前序遍历或者层次遍历，即跟在前的遍历方式，因此不能用中序遍历和后序遍历。

代码

• 递归，非常简单，前序遍历

/*
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* pRoot) {
        if(pRoot==NULL) return;
        TreeNode* temp;
        temp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = temp;
        Mirror(pRoot->left);
        Mirror(pRoot->right);
    }
};

• 迭代，队列方式，层次遍历

/*
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* pRoot) {
        if(pRoot==NULL) return;
        
        queue<TreeNode*> queueNode;
        queueNode.push(pRoot);
        while(!queueNode.empty()){
            TreeNode* p = queueNode.front();
            queueNode.pop();
            
            TreeNode* ptemp = p->left;
            p->left = p->right;
            p->right = ptemp;
            
            if(p->left) queueNode.push(p->left);
            if(p->right) queueNode.push(p->right);
        }
            
    }
};

• 迭代，栈的方式，前序遍历，代码和队列的方式是一样的，只不过效果上访问结点的顺序会不同

/*
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* pRoot) {
        if(pRoot==NULL) return;
        
        stack<TreeNode*> stackNode;
        stackNode.push(pRoot);
        while(!stackNode.empty()){
            TreeNode* p = stackNode.top();
            stackNode.pop();
            
            TreeNode* ptemp = p->left;
            p->left = p->right;
            p->right = ptemp;
            
            if(p->left) stackNode.push(p->left);
            if(p->right) stackNode.push(p->right);
        }
            
    }
};