剑指offer之面试题19：二叉树的镜像

题目：

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

二叉树的镜像定义：

源二叉树
                   8
                  /  \
                6   10
                / \  / \
              5  7 9 11

镜像二叉树
                  8
                 /  \
              10   6
               / \  / \
            11 9 7  5

思路：还是从根结点开始看，根结点，不用交换，看其左右子树，将其交换，然后在交换后的左右子树上，继续看子树的根结点，看这时的左右子树，进行交换；先交换，后递归

从上图看就是

（1）8为根结点 交换左右结点指向（6，10）--->（10，6）

                    8                    8
                  /  \                  /   \
                6   10    -->     10  6        
                / \  / \               / \  / \             

              5  7 9 11          9 11 5 7   

  (2)10为根结点 交换左右结点的指向 （9，11）--> (11,9)   

                    8                    8
                  /  \                  /   \
                10   6    -->     10  6        
                / \    / \             / \  / \             

              9 11  5 7         11 9 5 7

  (3)6为根结点  交换左右结点的指向  （5，7）--> (7,5)

                    8                    8
                  /  \                  /   \
                10   6    -->     10  6        
                / \    / \             / \  / \             

              11 9  5 7         11 9 7 5

     

/*
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;
        }
        if(pRoot->left!=NULL||pRoot->right!=NULL)
        {
            //先交换
            TreeNode *left=pRoot->right;
            TreeNode *right=pRoot->left;
            pRoot->left=left;
            pRoot->right=right;
        }
        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;
		stack<TreeNode*> s1;
        s1.push(pRoot);
        while(!s1.empty())
        {
            TreeNode *cur=s1.top();
            s1.pop();
            //先交换
           if(cur->left!=NULL||cur->right!=NULL)
            {
                TreeNode *left=cur->right;
            	TreeNode *right=cur->left;
            	cur->left=left;
            	cur->right=right;
                if(cur->left!=NULL)
                    s1.push(cur->left);
            	if(cur->right!=NULL)
                    s1.push(cur->right);
            }
        }
        
        
    }
};