首页 > 其他分享 >刷爆leetcode第十期

刷爆leetcode第十期

时间:2024-07-07 19:27:18浏览次数:21  
标签:return struct 第十期 isSameTree TreeNode NULL root leetcode

题目一 相同的树

给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

首先我们要来判断下它们的根是否相等

根相等的话是否它们的左子树相等

是否它们的右子树相等

一直到子树为空为止

大家仔细思考下这个思路对不对

接下来我们开始敲代码

首先我们想极端一点的情况

如果这个俩空指针

说明这里肯定不用判断了 返回ture就行

如果说有一个空指针 一个不为空指针的话 那么肯定是不相同的返回假就可以

接下来如果值相等 我们能判断它们相同嘛 显然不可以

所以说我们这里直接上两个不同 返回假

之后我们再判断它的左子树右子树

整体代码如下

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p==NULL&&q==NULL)
    {
        return true;
    }
    //一方为空
    if(p==NULL||q==NULL)
    {
      return false;
    }
    //都不为空
    if(p->val!=q->val)
    {
        return false;
    }
    return isSameTree(p->left,q->left)
    &&isSameTree(p->right,q->right);
}

测试一下 

可以运行

题目二 对称二叉树

这里和前面相同的数的思路差不多

都是判断极值条件

我们可以借用一下前面的代码稍微修改一下,将左右子树比较

之后递归展开 这里直接上代码 代码中会写明解题思路

 bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p==NULL&&q==NULL)
    {
        return true;
    }
    //一方为空
    if(p==NULL||q==NULL)
    {
      return false;
    }
    //都不为空
    if(p->val!=q->val)
    {
        return false;
    }
    return isSameTree(p->left,q->right)
    &&isSameTree(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root) {
    if(root==NULL)
    {
        return true;
    }

    return isSameTree(root->left,root->right);
}

这里我们要注意的是 要转换成两个子树问题才可以做

而子树问题需要再创建一个递归函数 可能是这一题的难点之一

还有一个难点就是要观察结构、

题目三 另一个树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/subtree-of-another-tree

我们这里只需要遍历一遍root 并且将root中的每一个节点和subroot比较一次就可以

遍历会吧

比较会吧

连起来

过啦!

代码表示如下

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
	if (p == NULL && q == NULL)
	{
		return true;
	}
	//一方为空
	if (p == NULL || q == NULL)
	{
		return false;
	}
	//都不为空
	if (p->val != q->val)
	{
		return false;
	}
	return isSameTree(p->left, q->left)
		&& isSameTree(p->right, q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root==NULL)
    {
        return false;
    }
    if(isSameTree(root,subRoot))
    {
        return true;
    }
    return isSubtree(root->left,subRoot)
    ||isSubtree(root->right,subRoot);
}

 以上便是本文所有内容,如有错误请各位大佬不吝赐教,感谢留言 

标签:return,struct,第十期,isSameTree,TreeNode,NULL,root,leetcode
From: https://blog.csdn.net/Zbldx/article/details/140250606

相关文章

  • Leetcode刷题记录1 哈希+双指针+滑动窗口
    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章目录前言hot1001.哈希#1.两数之和#49.字母异位词分组#128.最长连续序列2.双指针#283.移动零#11.盛最多水的容器#15.三数之和#42.接雨水3.滑动窗口#3.无重复字符的最长子串#438.找到字符串中所有......
  • [Leetcode]经典算法
    检测环快慢指针法是一种用于检测链表中是否存在环的有效方法,同时也可以找到环的起点。该方法的原理基于两个指针在链表上同时移动,其中一个移动得更快,而另一个移动得更慢。检测环的存在:使用两个指针,一个称为快指针(fast),一个称为慢指针(slow)。在每一步中,快指针向前移动两步,而慢......
  • leetcode678:有效的括号字符串
    给你一个只包含三种字符的字符串,支持的字符类型分别是 '('、')' 和 '*'。请你检验这个字符串是否为有效字符串,如果是 有效 字符串返回 true 。有效 字符串符合如下规则:任何左括号 '(' 必须有相应的右括号 ')'。任何右括号 ')' 必须有相应的左括号 '(' 。左括......
  • 【LeetCode 0024】【链表】交换单链表相邻两个节点
    SwapNodesinPairsGivena linkedlist,swapeverytwoadjacentnodesandreturnitshead.Youmustsolvetheproblemwithout modifyingthevaluesinthelist’snodes(i.e.,onlynodesthemselvesmaybechanged.)Example1:**Input:**head=[1,2,3......
  • 【LeetCode 0141】【链表】【双指针之快慢指针】判断给定单链表是否存在环
    LinkedListCycleGivenhead,theheadofalinkedlist,determineifthelinkedlisthasacycleinit.Thereisacycleinalinkedlistifthereissomenodeinthelistthatcanbereachedagainbycontinuouslyfollowingthe next pointer.Internal......
  • [LeetCode] 1366. Rank Teams by Votes 通过投票对团队排名
    Inaspecialrankingsystem,eachvotergivesarankfromhighesttolowesttoallteamsparticipatinginthecompetition.Theorderingofteamsisdecidedbywhoreceivedthemostposition-onevotes.Iftwoormoreteamstieinthefirstposition,wecon......
  • leetcode 257. 二叉树的所有路径
    给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。 示例1:输入:root=[1,2,3,null,5]输出:["1->2->5","1->3"]示例2:输入:root=[1]输出:["1"]java解题思路及代码实现递归法packagecom.java......
  • leetcode 102. 二叉树的层序遍历
    给你二叉树的根节点 root ,返回其节点值的 层序遍历 。(即逐层地,从左到右访问所有节点)。示例1:输入:root=[3,9,20,null,null,15,7]输出:[[3],[9,20],[15,7]]示例2:输入:root=[1]输出:[[1]]示例3:输入:root=[]输出:[]提示:树中节点数目在范围 [0,2000] ......
  • leetcode77组合——经典回溯算法
    本文主要讲解组合的要点与细节,以及回溯算法的解题步骤,按照步骤思考更方便理解 c++和java代码如下,末尾给定两个整数 n 和 k,返回范围 [1,n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。 具体要点:1.首先,这道题的暴力解法是k层for循环,遍历所有的......
  • 【LeetCode:3101. 交替子数组计数 + 滑动窗口 + 数学公式】
    ......