力扣Leetcode 572. 另一个树的子树
2024-10-09 12:19:47
另一个树的子树
给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
3
/ \
4 5
/ \
1 2
给定的树 t:
4
/ \
1 2
返回 true,因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s:
3
/ \
4 5
/ \
1 2
/
0
给定的树 t:
4
/ \
1 2
返回 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 isSametree(struct TreeNode* s, struct TreeNode* t){
if (s == NULL && t == NULL) return true;// 遍历到空时 返回true
return s && t // 都不为空时依次判断
&& s->val == t->val // 首先s与t的值相等
&& isSametree(s->left, t->left) // s t的左子树递归
&& isSametree(s->right, t->right); // s t的右子树递归
}
/* 判断子树的主函数 */
bool isSubtree(struct TreeNode* s, struct TreeNode* t) {
if (s == NULL && t == NULL) return true; // 都为空时 true
if (s == NULL && t != NULL) return false; // s空 t非空 false
return isSametree(s, t) // 第一种情况:s,t第一个节点就相同
|| isSubtree(s->left, t)// 第二种:t为s的左子树中一棵
|| isSubtree(s->right, t); // 第三种:t为s右子树中一课
}
};
最新文章
- 严重: Error configuring application listener of class org.springframework.web.context.ContextLoaderListener
- A daemon process class in python
- Unrecognized selector sent to instance xxxxxxx
- CXF之六 自定义拦截器
- [1.1]Knowledge that should be prepared
- Linux下对后台进程通过kill传递信号不起作用的问题
- sql 时间转换问题 from_unixtime() UNIX_TIMESTAMP()
- linux shell中获取mongodb最大连接数、内存使用情况等
- 为什么开源外围包安装指导都是按照到/usr/local/目录下,/usr/local与/usr的区别
- 卷积神经网络(matlab实现)
- HDU 5754 Life Winner Bo(各类博弈大杂合)
- Unity3D架构设计NavMesh寻路
- Scala_数据结构
- [转]javaweb学习总结(二十九)——EL表达式
- pxe前期接入H3C交换机网络准备
- Red Hat 6.5 Samba服务器的搭建(匿名访问,免登录)
- JavaScript入门详解
- 可软件定义的存储逻辑——Efficient and agile storage management in software defined environments
- OrCAD Capture出现丢失cdn_sfl401as.dll问题
- PM2自动发布本地项目到服务器
热门文章
- CF R638 div2 F Phoenix and Memory 贪心 线段树 构造 Hall定理
- 这届 Showgirl行不行?AI告诉你谁是ChinaJoy上最漂亮的小姐姐
- rabbitMQ结合spring-boot使用(1)
- python6.2类的封装
- JDK11.0.7下载及安装详细教程(win10)
- 用Python来搞副业?这届大学生到底有多野……
- Linux学习笔记之如何把ubuntu下的c文件共享到windows下文件夹
- C#LeetCode刷题之#20-有效的括号(Valid Parentheses)
- C#LeetCode刷题之#263-丑数(Ugly Number)
- ssh断连后,保持Linux后台程序连接