本文主要是介绍力扣第572题 另一棵树的子树 c++深度(DFS)注释版,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
572. 另一棵树的子树
简单
给你两棵二叉树 root
和 subRoot
。检验 root
中是否包含和 subRoot
具有相同结构和节点值的子树。如果存在,返回 true
;否则,返回 false
。
二叉树 tree
的一棵子树包括 tree
的某个节点和这个节点的所有后代节点。tree
也可以看做它自身的一棵子树。
示例 1:
输入:root = [3,4,5,1,2], subRoot = [4,1,2] 输出:true
示例 2:
输入:root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] 输出:false
提示:
root
树上的节点数量范围是[1, 2000]
subRoot
树上的节点数量范围是[1, 1000]
-104 <= root.val <= 104
-104 <= subRoot.val <= 104
思路和解题方法
bool check(TreeNode *o, TreeNode *t)
:这个函数检查两个节点是否相同,o
表示s
的节点,t
表示t
的节点。该函数使用递归方法判断两个节点是否相同,如果它们的值相等并且左右子树也相等,则返回true
,否则返回false
。
if(!o && !t)
:如果s
和t
都为空,则true
,这意味着t
是s
的子树。
if((o&&!t)||(!o&&t)||(o->val!=t->val))
:如果只有o
或只有t
为空,或者它们的值不相等,这说明t
不能是子树,返回false
。
return check(o->left,t->left)&&check(o->right,t->right)
:如果它们的值相等,并且左右子树也相等,则返回true
。该函数的返回方式是通过递归调用自己进行判断的。
bool dfs(TreeNode *o, TreeNode *t)
:该函数使用递归,沿着s
向下遍历所有节点。如果在某个节点的子树中存在t
,则返回true
。如果整个树都遍历完了,还没有发现任何t
的子树,则返回false
。
return check(o,t)|| dfs(o->left,t)||dfs(o->right,t)
:用于判断当前节点是否为t
的子树,如果是,则返回true
。如果不是,则递归调用此函数来遍历s
的左右子树。如果任何一个子树包含t
,则返回true
,否则返回false
。
bool isSubtree(TreeNode *s, TreeNode *t)
:该函数是该算法的入口,它接受两个参数s
和t
,分别表示主树和子树。它使用深度优先搜索遍历s
上的每个节点,并调用dfs
和check
函数来检查t
是否是s
的子树。如果t
是s
的子树,则返回true
,否则返回false
。
复杂度
时间复杂度:
O(m*n)
check
函数的时间复杂度是O(n),其中n是树的节点数,因为最坏情况下需要比较所有节点的值。dfs
函数的时间复杂度是O(m*n),其中m是主树的节点数,n是子树的节点数。因为在最坏情况下,需要遍历主树的每个节点,并调用check
函数进行比较。所以总体上,算法的时间复杂度可以表示为O(m*n),其中m是主树的节点数,n是子树的节点数。
空间复杂度
O(n)
- 空间复杂度由递归调用造成的函数调用栈占用的空间决定。在最坏情况下,树的高度可以达到n,所以空间复杂度是O(n)。
c++ 代码
class Solution {
public:// 检查两个节点是否相同bool check(TreeNode *o, TreeNode *t) {if (!o && !t) return true; // 如果都为空,则返回trueif ((o && !t) || (!o && t) || (o->val != t->val)) return false; // 如果其中一个为空或值不相等,则返回falsereturn check(o->left, t->left) && check(o->right, t->right); // 递归调用自己比较左右子树是否相等}// 深度优先搜索遍历主树,判断是否存在子树tbool dfs(TreeNode *o, TreeNode *t) {if (!o) return false; // 如果o为空树,则不存在子树treturn check(o, t) || dfs(o->left, t) || dfs(o->right, t); // 判断当前节点是否为子树,如果不是,则递归地遍历左右子树}// 判断是否为子树bool isSubtree(TreeNode *s, TreeNode *t) {return dfs(s, t);}
};
觉得有用的话可以点点赞,支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。
这篇关于力扣第572题 另一棵树的子树 c++深度(DFS)注释版的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!