【Leetcode】965. 单值二叉树、100. 相同的树、572. 另一棵树的子树

简介: 【Leetcode】965. 单值二叉树、100. 相同的树、572. 另一棵树的子树

作者:一个喜欢猫咪的的程序员

专栏:《Leetcode》

喜欢的话:世间因为少年的挺身而出,而更加瑰丽。                                  ——《人民日报》

目录

965. 单值二叉树

100. 相同的树

572. 另一棵树的子树


965. 单值二叉树


965. 单值二叉树

https://leetcode.cn/problems/univalued-binary-tree/


题目描述:

如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时,才返回 true;否则返回 false


示例:

思路:

左右节点都不为NULL,当root跟它的左右节点其中一个不相等时,就不是单值二叉树。当root的左右节点有一个为NULL,只需要比较另外一个不为NULL是否与root相等就可以了。这样递归就可以完成。


代码实现:

bool isUnivalTree(struct TreeNode* root){
    if(root==NULL)
    return true;
    if(root->left&&root->left->val!=root->val)
    return false;
    if(root->right&&root->right->val!=root->val)
    return false;
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}


100. 相同的树


100. 相同的树

https://leetcode.cn/problems/same-tree/


题目描述:

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

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


示例:

思路:

当p和q都不为NULL时,对应的节点相等,就递归他们左右节点继续判断。否则return false。

只有当p和q都为NULL时,return true。


代码实现:

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p==NULL&&q==NULL)
    return true;
    if(p&&q)
    {
    if(p->val==q->val)
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    else
    return false;
    }
    else
    return false;
}


572. 另一棵树的子树


572. 另一棵树的子树

https://leetcode.cn/problems/subtree-of-another-tree/


题目描述:


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


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


示例:

思路:

利用上题相同的数的代码作为函数。

当树相等时,直接放回true。否则直接遍历每一个子树,当有一个子树相等时就返回true,否则返回false。


代码实现:

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p==NULL&&q==NULL)
    return true;
    if(p&&q)
    {
    if(p->val==q->val)
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    else
    return false;
    }
    else
    return false;
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root==NULL)
    return false;
    if(isSameTree(root,subRoot))
    return true;
    else
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}


相关文章
|
4月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
40 2
|
4月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
37 2
|
4月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
35 0
|
4月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
32 0
|
4月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
34 0
|
4月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
39 0
|
4月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
32 0
|
5月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
6月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
78 6
|
6月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
151 2