剑指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);
}

           

想想如何用循环、迭代解决！！！