題目

請實現(xiàn)一個函數(shù)，用來判斷一棵二叉樹是不是對稱的。如果一棵二叉樹和它的鏡像一樣，那么它是對稱的。例如，在如圖4.3所示的3棵二叉樹中，第一棵二叉樹是對稱的，而另外兩棵不是

download-1.png

思路

• 思路一

使用遞歸實現(xiàn)，根節(jié)點的左右子樹相同，左子樹的左子樹和右子樹的右子樹相同，左子樹的右子樹和右子樹的左子樹相同即可

• 思路二

使用非遞歸，采用?；蜿犃写嫒「骷壸訕涓?jié)點

算法實現(xiàn)

定義二叉樹

#include <iostream>
using namespace std;

struct BinaryTreeNode {
    int m_nValue;
    BinaryTreeNode *m_pLeft;
    BinaryTreeNode *m_pRight;
};

遞歸

bool isSymmetrical(BinaryTreeNode *pRoot1, BinaryTreeNode *pRoot2);

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_pLeft, pRoot2->m_pRight) &&
    isSymmetrical(pRoot1->m_pRight, pRoot2->m_pLeft);
}

非遞歸（棧）

bool isSymmetricalStack(BinaryTreeNode *pRoot)
{
    if(pRoot == nullptr) return true;
    // 使用單棧
    stack<BinaryTreeNode *> stack;

    // 入棧
    stack.push(pRoot->m_pLeft);
    stack.push(pRoot->m_pRight);

    while(!stack.empty()) {
        // 成對取出
        BinaryTreeNode *rightNode = stack.top();
        stack.pop();
        BinaryTreeNode *leftNode = stack.top();
        stack.pop();

        // 若都為空，繼續(xù)
        if(leftNode == nullptr && rightNode == nullptr) continue;
        // 一個為空，返回false
        if(leftNode == nullptr || rightNode == nullptr) return false;
        // 不為空，比較當(dāng)前值，值不等，返回false；
        if(leftNode->m_nValue != rightNode->m_nValue) return false;

        // 確定入棧順序，每次入棧都是成對成對的
        stack.push(leftNode->m_pLeft);
        stack.push(rightNode->m_pRight);
        stack.push(leftNode->m_pRight);
        stack.push(rightNode->m_pLeft);
    }
    return true;
}

非遞歸（隊列）

bool isSymmetricalQueue(BinaryTreeNode *pRoot)
{
    if(pRoot == nullptr) return true;
    // 使用兩個隊列
    queue<BinaryTreeNode *> queue1, queue2;
    queue1.push(pRoot->m_pLeft);
    queue2.push(pRoot->m_pRight);

    BinaryTreeNode *leftNode, *rightNode;

    while(!queue1.empty() && !queue2.empty()) {
        // 成對取出
        leftNode= queue1.front();
        queue1.pop();
        rightNode= queue2.front();
        queue2.pop();

        if(leftNode == nullptr && rightNode == nullptr) continue;
        if(leftNode == nullptr || rightNode == nullptr) return false;
        if(leftNode->m_nValue != rightNode->m_nValue) return false;

        // 成對插入
        queue1.push(leftNode->m_pLeft);
        queue1.push(leftNode->m_pRight);
        queue2.push(rightNode->m_pRight);
        queue2.push(rightNode->m_pLeft);
    }
    return true;
}

參考

《劍指offer》
對稱二叉樹