转载

每天一个编程题·iOS开发算法提升计划（1）

1. 题目

请实现一个函数，用来判断一棵二叉树是不是对称的：如果一颗二叉树和它的镜像一样，那么它是对称的。

2. 解析

两层节点：对称的情况分析

两个父节点的值对称（相等）
左父节点的左子节点与右父节点的右子节点对称
左父节点的右子节点与右父节点的左子节点对称

第三层节点：采用递归

根节点：根节点作为两个父节点进行输入

3. 参考

SymmetricalBinaryTree.cpp

include #include "../Utilities/BinaryTree.h"

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

BinaryTree.cpp

#include #include "BinaryTree.h"
BinaryTreeNode* CreateBinaryTreeNode(int value)
{
    BinaryTreeNode* pNode = new BinaryTreeNode();
    pNode->m_nValue = value;
    pNode->m_pLeft = nullptr;
    pNode->m_pRight = nullptr;
    return pNode;
}

void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)
{
    if(pParent != nullptr)
    {
        pParent->m_pLeft = pLeft;
        pParent->m_pRight = pRight;
    }
}

void PrintTreeNode(const BinaryTreeNode* pNode)
{
    if(pNode != nullptr)
    {
        printf("value of this node is: %d/n", pNode->m_nValue);
        if(pNode->m_pLeft != nullptr)
            printf("value of its left child is: %d./n", pNode->m_pLeft->m_nValue);
        else
            printf("left child is nullptr./n");
        if(pNode->m_pRight != nullptr)
            printf("value of its right child is: %d./n", pNode->m_pRight->m_nValue);
        else
            printf("right child is nullptr./n");
    }
    else
    {
        printf("this node is nullptr./n");
    }
    printf("/n");
}

void PrintTree(const BinaryTreeNode* pRoot)
{
    PrintTreeNode(pRoot);
    if(pRoot != nullptr)
    {
        if(pRoot->m_pLeft != nullptr)
            PrintTree(pRoot->m_pLeft);
        if(pRoot->m_pRight != nullptr)
            PrintTree(pRoot->m_pRight);
    }
}

void DestroyTree(BinaryTreeNode* pRoot)
{

    if(pRoot != nullptr)
    {
        BinaryTreeNode* pLeft = pRoot->m_pLeft;
        BinaryTreeNode* pRight = pRoot->m_pRight;
        delete pRoot;
        pRoot = nullptr;
        DestroyTree(pLeft);
        DestroyTree(pRight);
    }
}