每日一题:LeetCode-LCR 143.子结构判断

简介: 每日一题:LeetCode-LCR 143.子结构判断

每日一题系列(day 05)

前言:

🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈

   🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉算法👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇,我们要做的,就是斩妖除魔💥💥,打怪升级!💪💪当然切记不可😈走火入魔😈,每日打怪,日日累积,终能成圣🙏🙏!开启我们今天的斩妖之旅吧!✈️✈️


题目:

   给定两棵二叉树 tree1 和 tree2,判断 tree2 是否以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。注意,空树 不会是以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。

示例1:

示例2:

注意事项:

  • 0 <= 节点个数 <= 10000

思路:

  首先我们来思考,一棵树的结构有哪些情况?

1、B树为空或者AB都为空的情况,但是题目明确要求了,AB有一个为空,都不为另一棵树的子结构,所以第一点情况是false。

2、B树是A树的一颗子树,这个肯定满足时A的子结构。

3、B树是A树的一部分,并非子树,题目示例也说明了这种B树是A树的子结构。

那么我们来看看这三点能总结出什么规律?A树B树必须都不为空树,而且B树一定要是A树的一部分结构或者就是A树,这才能满足B是A的子结构。

  1、首先,A树与B树都不能为NULL,如果为NULL直接返回false。

  2、接下来就要判断A的当前节点是否与B的根节点的值相等,如果相等则从这里开始匹配,看是否能够匹配成功,成功直接返回true即可。

  3、进入到匹配函数,如果遍历到的A的当前节点为空,B的节点也为空,则表示匹配成功,如果A为空,B不为空就是匹配失败。如果匹配的当前B节点为空,A不为空,也表示B树是A树的子结构则返回true。

  4、为空的情况我们判断完了,就要判断A,B节点的值是否相等了,不相等也是返回false,到了这一步,还没返回说明我们还要继续往下遍历,所以这个时候我们就需要分别向A树B树的左右子树遍历了。函数结束。

  5、如果当前节点不匹配,那么就向A的左子树查找,是否存在于B树根节点所匹配的节点,如果有就再次匹配…同理,如果左子树没有此节点,那么向右子树遍历。

  6、当左右子树都遍历完成之后,也没有匹配的节点,那么就说明A树中没有B树这样的子结构,这时我们返回false即可。

代码实现:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool match(TreeNode *A, TreeNode *B)
    {
        if(A == NULL) return B == NULL;//如果A当前节点为空且B的节点也为空则表示匹配成功,否则如果A为空,B不为空就匹配失败。
        if(B == NULL) return true;//如果此时B已经为空了,说明前面已将匹配了,返回true即可
        if(A -> val != B -> val) return false;//只要两个值不相等就直接返回false
        return match(A -> left, B -> left) && match(A -> right, B -> right);//向两棵树的左子树和右子树遍历,遍历完成之后
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A == NULL || B == NULL) return false;//根据题目意思,如果A为空或者B为空时,都不满足子树结构
        if(A -> val == B -> val && match(A, B)) return true;//进行比较,如果A树的值与B树的值相等则从当前节点开始匹配。
        if(isSubStructure(A -> left, B)) return true;//匹配不成功向A的左子树与B的根节点匹配
        if(isSubStructure(A -> right, B)) return true;//同理向A的右子树与B的根节点匹配
        return false;//匹配的情况全部没了,剩下的就是不匹配的情况
    }
};

  这样我们就完成了二叉树子结构判断的一道题目了,题目理解不是很难,主要是一些边界条件并不是很容易想,想不全就总有几个测试用例过不了。

相关文章
|
7月前
【每日一题Day331】LC2560打家劫舍 IV | 二分查找 + 贪心
【每日一题Day331】LC2560打家劫舍 IV | 二分查找 + 贪心
39 0
|
算法 搜索推荐
【LeetCode力扣】LCR170 使用归并排序的思想解决逆序对问题(详细图解)
【LeetCode力扣】LCR170 使用归并排序的思想解决逆序对问题(详细图解)
93 0
|
2月前
|
存储
Leetcode第十五题(三数之和)
LeetCode第十五题“三数之和”要求在一个整数数组中找出所有不重复的三元组,使得它们的和为0,通常通过先排序再使用双指针法来解决。
38 0
Leetcode第十五题(三数之和)
|
6月前
【洛谷 P1219】[USACO1.5]八皇后 Checker Challenge 题解(深度优先搜索+回溯法)
**USACO1.5八皇后挑战**是关于在$n\times n$棋盘上放置棋子的,确保每行、每列及两条主对角线上各有一个且仅有一个棋子。给定$6$作为输入,输出前$3$个解及解的总数。例如,对于$6\times6$棋盘,正确输出应包括解的序列和总数。代码使用DFS解决,通过跟踪对角线占用状态避免冲突。当找到所有解时,显示前三个并计数。样例输入$6$产生输出为解的前三个排列和总数$4$。
40 0
|
7月前
|
算法
【数据结构与算法 | 基础篇】[链表专题]力扣LCR077, 83
【数据结构与算法 | 基础篇】[链表专题]力扣LCR077, 83
|
7月前
|
算法 测试技术
每日一题:LeetCode-LCR 007. 三数之和
每日一题:LeetCode-LCR 007. 三数之和
|
C语言
力扣 LCR 024. 反转链表两种解法
C语言实现的代码解题思路
74 1
|
机器学习/深度学习 算法 Java
刷爆 LeetCode 周赛 337,位掩码/回溯/同余/分桶/动态规划·打家劫舍/贪心
上周末是 LeetCode 第 337 场周赛,你参加了吗?这场周赛第三题有点放水,如果按照题目的数据量来说最多算 Easy 题,但如果按照动态规划来做可以算 Hard 题。
119 0
Leetcode-每日一题1250. 检查「好数组」(裴蜀定理)
版权声明:本文为博主原创文章,未经博主允许不得转载。https://blog.csdn.net/weixin_46618592/article/details/129038912?spm=1001.2014.3001.5502
133 0
Leetcode-每日一题1250. 检查「好数组」(裴蜀定理)
【力扣】 丑数 来,和我上一节数学课吧~
【力扣】 丑数 来,和我上一节数学课吧~
105 0
【力扣】 丑数 来,和我上一节数学课吧~