劍指offer 28： 對稱的二叉樹（遞歸實作）

• 題目

  實作一個函數，用來判斷一棵二叉樹是不是對稱的。如果一顆二叉樹和它的鏡像一樣那麼它對稱。

• 分析
• 存在三種周遊算法，前序周遊，中序周遊，後序周遊。我們可以針對前序周遊定義一種對稱的周遊算法。即先周遊父節點，再周遊右結點，最後周遊左結點。
• 以上面的為例，先序周遊為：8 ， 6， 5， 7， 6， 7， 5
• 我們定義的周遊方式周遊為： 8 ，6，5, 7， 6 ， 7， 5
• 我們注意到是一樣的。然後再看特殊的例子：

  

• 上圖用前序周遊 為：7 ，7, 7 , 7, 7 , 7
• 用定義的周遊算法也為： 7， 7， 7， 7， 7, 7
• 不過他們并不對稱，思考：隻要我們把遇到nullptr指針也考慮進來就可以了。

其實也可以有兩種方式解決問題，就像前序周遊一樣：遞歸和疊代。

遞歸實作：

struct BinaryTreeNode
{
    int             m_nValue;
    BinaryTreeNode* m_left;
    BinaryTreeNode* m_right;
} ;
bool isSymmetrical(BinaryTreeNode* pRoot)
{
    return isSymmetrical(pRoot,pRoot);
}

bool isSymmetrical(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
{
    if(pRoot1 == nullptr  && pRoot2 == nullptr)
        return true;
    
    if(pRoot1 == nullptr  || pRoot2 == nullptr)
    {
        return false;
    }
    
    if(pRoot1->m_nValue != pRoot2->m_nValue)
        return false;
    
    return isSymmetrical(pRoot1->m_left, pRoot2->m_right) && isSymmetrical(pRoot1->m_right, pRoot2->m_left);
}

           

想想如何用循環、疊代解決！！！