剑指offer - 对称的二叉树

题目

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。例如，在如图4.3所示的3棵二叉树中，第一棵二叉树是对称的，而另外两棵不是

download-1.png

思路

• 思路一

使用递归实现，根节点的左右子树相同，左子树的左子树和右子树的右子树相同，左子树的右子树和右子树的左子树相同即可

• 思路二

使用非递归，采用栈或队列存取各级子树根节点

算法实现

定义二叉树

#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();

        // 若都为空，继续
        if(leftNode == nullptr && rightNode == nullptr) continue;
        // 一个为空，返回false
        if(leftNode == nullptr || rightNode == nullptr) return false;
        // 不为空，比较当前值，值不等，返回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》
对称二叉树