剑指Offer-树的子结构

题解

 // 树的子结构
        bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
        {
            // 初始化:树A和树B的根节点pRoot1, pRoot2
            // 遍历树A,cur指向当前节点,将cur作为根节点的子树C与pRoot2作为根节点的子树进行比较,若后者是前者的子结构,则返回true否则为false
            if (!pRoot1 || !pRoot2) return false;
            return is_equ(pRoot1, pRoot2) || is_equ(pRoot1->left, pRoot2) || is_equ(pRoot1->right, pRoot2);
        }

//        // 树的先序遍历
//        void pre(TreeNode* root)
//        {
//            // 对root做点什么
//            pre(root->left);
//            pre(root->right);
//        }

        // 判断是否有相同的结构
        bool is_equ(TreeNode* pRoot1, TreeNode* pRoot2){
            // 初始化,两颗子树的根节点,pRoot1, pRoot2
            // 若pRoot1和pRoot2的内容不等,直接返回false, 若相等则递归判断其左子树和右子树是否相等
            // 若pRoot1为空,pRoot2不为空,则判为false
            // 若pRoot1不为空,pRoot2为空,则判为true
            if (!pRoot2) return true;  // pRoot2为空
            if (!pRoot1) return false;
            return (pRoot1->val==pRoot2->val) && is_equ(pRoot1->left, pRoot2->left) && is_equ(pRoot1->right, pRoot2->right);
        }

难点

  1. 第7行,顶层设计,即判断树B是树A的子结构的条件:(1)树B是以树A为根节点的树的子结构;(2)树B是以树A的左子树中的子结构;(3)树B是树A中右子树的子结构;
  2. 第19,26行,设计以pRoot2为根节点的树是否是以pRoot1为根节点的递归函数
全部评论

相关推荐

所有差评都记到我三国杀账上:找廉价劳动力罢了
点赞 评论 收藏
分享
2024-12-09 16:42
门头沟学院 Java
程序员牛肉:我愿称你这种简历为npc简历。特点就是毫无任何亮点。你简历没有任何问题,但就是太普通了。实在是太普通了。 你可以在牛客搜一搜有多少人的简历和你一摸一样。一个大一点的公司一天能收几百份简历,你要是有公司邮箱的话,你可以尝试一下。在这几百份简历中,面试官面试一个人就需要1个小时。一天最多面试5个人。 照这样算,一个部门抽出3个人来面试,一天面试15个人。10天也最多面试150个人。在如此悬殊的投递和面试比之下,面试官一天要翻大量的简历。你这种简历真的是毫无亮点,面试官真的很难激起面试你的欲望。 没有学历,没有好的项目,技术也一般。写简历真的是给人乱写的感觉。 第一个项目中,使用mybatis plus这个插件来和数据库进行交互也可以作为亮点吗?基于nacos实现一个微服务中的服务注册也算亮点?第二个项目还是黑马点评。像有这种项目的简历一抓一大把。 问题来了:你觉得面试官为什么会面试你?在简历大致相同的情况下,你学校又是个二本,你认为面试官选择你而不选择学历更高的同学的原因是什么? 所以我觉得对于你来讲,可以一边投递实习,一边准备新的项目。同时积极去探索一些自己能够写到简历上的亮点。比如是不是有自己的公众号或者博客。比如是不是有自己开源项目,比如是不是一些含金量比较高的比赛 想要有面试机会的第一步就是让自己从这种npc简历中跳出来,最起码有一点“活人”的气息
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务