每日一题系列(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;//匹配的情况全部没了,剩下的就是不匹配的情况 } };
这样我们就完成了二叉树子结构判断的一道题目了,题目理解不是很难,主要是一些边界条件并不是很容易想,想不全就总有几个测试用例过不了。