手撸二叉树之另一棵树的子树
Hello, 大家好,今天是我参加 8 月更文的第 23 天,今天给大家带来的关于二叉树相关的算法题是另一棵树的子树,正文如下:
题目
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例 1:
复制代码
示例 2:
复制代码
解题思路
根据题意,要判断一个树 t 是否是另一个树 s 的子树,那么可以判断树 t 是否和树 s 的任意子树相等。
判断树 t 是否是 s 的子树,存在以下三种情况:
t 和 s 完全相同;
t 是 s 左子树中的某个部分;
t 是 s 右子树的某个部分;
我们可以使用深度优先搜索然后枚举树 s 中的每一个节点,判断这个节点的子树是否和树 t 相等。
代码实现
复制代码
最后
复杂度分析:
时间复杂度:对于每一个 s 上的点,都需要做一次深度优先搜索来和 t 匹配,匹配一次的时间代价是 O(|t|),那么总的时间代价就是 O(|s|x|t|)。故渐进时间复杂度为 O(|s|x|t|)。
空间复杂度:假设 s 的深度为 ds, t 的深度为 dt,任意时刻栈空间的最大使用代价是 O(max(ds,dt))。
版权声明: 本文为 InfoQ 作者【HelloWorld杰少】的原创文章。
原文链接:【http://xie.infoq.cn/article/0e09bb6a3330cc68e42612a26】。文章转载请联系作者。
评论