二叉樹面試題之二叉樹鏡像

首先分析，互為鏡像，也就是說，一個節點的左右子樹互相交換位置，是以采用遞歸的方法較為簡單，且友善了解，即鏡像步驟：

1）.交換根結點的左右子樹節點。

2）.交換左子樹（以圖中10為例）的左右節點。

3）.交換右子樹（以圖中6為例）的左右結點。

總結上面過程，一顆樹的鏡像過程：先前序周遊樹的每個節點，如果周遊到節點有子節點，就交換它的兩個子節點，當交換完所有非葉子節點的左右子節點之後，就得到了樹的鏡像。

實作如下：

struct BinaryTreeNode
{
	int value;
	BinaryTreeNode*_left;
	BinaryTreeNode*_right;
};
void Mirror(BinaryTreeNode*Node)
{
	if (Node == NULL)
		return; 
	if (Node->_left == NULL&&Node->_right == NULL)
		return;
	BinaryTreeNode*tmp = Node->_left;
	Node->_left = Node->_right;
	Node->_right = tmp;
	if (Node->_left)
		Mirror(Node->_left);
	if (Node->_right)
		Mirror(Node->_right);
}
           

//以先序的方式建構二叉樹，輸入-1表示結點為空  
void CreateBinaryTree(BinaryTreeNode *&pRoot)  
{  
    int nNodeValue = 0;  
    cin >> nNodeValue;      
    if (-1 == nNodeValue)  
    {  
        return;   
    }  
    else  
    {  
        pRoot = new BinaryTreeNode();  
        pRoot->m_nValue = nNodeValue;  
        CreateBinaryTree(pRoot->m_pLeft);  
        CreateBinaryTree(pRoot->m_pRight);  
    }  
}  
  
void PrintInOrder(BinaryTreeNode *&pRoot)  
{  
    if (pRoot != NULL)  
    {  
        PrintInOrder(pRoot->m_pLeft);  
        cout << pRoot->m_nValue << " ";  
        PrintInOrder(pRoot->m_pRight);  
    }  
}