β

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

Harries Blog™ 6 阅读

1. 题目

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

2. 解析

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

第三层节点:采用递归

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

3. 参考

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

作者:陈满iOS

链接: https ://www.jianshu.com/p/e933f948c784

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。 PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处: Harries Blog™ » 每天一个编程题·iOS开发算法提升计划(1)

作者:Harries Blog™
追心中的海,逐世界的梦
原文地址:每天一个编程题·iOS开发算法提升计划(1), 感谢原作者分享。

发表评论