劍指offer之面試題19：二叉樹的鏡像

題目：

操作給定的二叉樹，將其變換為源二叉樹的鏡像。

二叉樹的鏡像定義：

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

鏡像二叉樹
                  8
                 /  \
              10   6
               / \  / \
            11 9 7  5

思路：還是從根結(jié)點(diǎn)開始看，根結(jié)點(diǎn)，不用交換，看其左右子樹，將其交換，然后在交換后的左右子樹上，繼續(xù)看子樹的根結(jié)點(diǎn)，看這時(shí)的左右子樹，進(jìn)行交換；先交換，后遞歸

從上圖看就是

（1）8為根結(jié)點(diǎn) 交換左右結(jié)點(diǎn)指向（6，10）--->（10，6）

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

              5  7 9 11          9 11 5 7   

  (2)10為根結(jié)點(diǎn) 交換左右結(jié)點(diǎn)的指向 （9，11）--> (11,9)   

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

              9 11  5 7         11 9 5 7

  (3)6為根結(jié)點(diǎn)  交換左右結(jié)點(diǎn)的指向  （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);
        
    }
};

思路二：利用棧的性質(zhì)，進(jìn)行循環(huán)訪問根結(jié)點(diǎn)，交換其左右

代碼：

/*
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);
            }
        }
        
        
    }
};