广度优先遍历 BFS
解题思路
使用 层序遍历 进行遍历，队列里面会放置二叉树每一层的节点；
对每个遍历的节点与 subRoot 比较是否是同一棵树，如果是同一棵树则找到了子树，否则没有找到；
比较是否是同一颗树，可参考 leetcode🧑💻 100. 相同的树；
复杂度
-
时间复杂度：
0(st)，对于每一个 S 上的点，都需要做一次深度优先搜索来和 t 匹配，匹配一次的时间代价是0(t)； -
空间复杂度：
O(N)，其中 N 是链表的最大长度；
代码实现
var isSubtree = function (root, subRoot) {
if (root === null) return false;
const queue = [root]; // 声明队列用于存储后续数据
while (queue.length) {
const node = queue.shift();
if (isSameTree(node, subRoot)) return true;
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
return false;
};
var isSameTree = function (p, q) {
// p、q 都为空，则两棵树相同
if (p === null && q === null) return true;
// p、q 两棵树有一颗为空，则两棵树不同
if (p === null || q === null) return false;
// p、q 两棵树根节点的值不同，则两棵树不同
if (p.val !== q.val) return false;
// 继续判断 p、q 的左右子节点是否相同
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};
深度优先遍历 DFS
解题思路
这是一种最朴素的方法——深度优先搜索枚举 s 中的每一个节点，判断这个点的子树是否和 t 相等；
如何判断一个节点的子树是否和 t 相等呢，又需要做一次深度优先搜索来检查，即让两个指针一开始先指向该节点和 t 的根，然后「同步移动」两根指针来「同步遍历」这两棵树，判断对应位置是否相等；
复杂度
-
时间复杂度：
0(st)，对于每一个 S 上的点，都需要做一次深度优先搜索来和 t 匹配，匹配一次的时间代价是0(t)； -
空间复杂度：
O(max{ds,dt})，假设 S 深度为 ds ，t 的深度为 dt，任意时刻栈空间的最大使用代价是 O(max{ds,dt})；
代码实现
var isSubtree = function (root, subRoot) {
if (root === null) return false;
if (root.val === subRoot.val && isSameTree(root, subRoot)) return true;
// 不停地比较，某一个子树，是不是和 subRoot 一样
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
};
var isSameTree = function (p, q) {
// p、q 都为空，则两棵树相同
if (p === null && q === null) return true;
// p、q 两棵树有一颗为空，则两棵树不同
if (p === null || q === null) return false;
// p、q 两棵树根节点的值不同，则两棵树不同
if (p.val !== q.val) return false;
// 继续判断 p、q 的左右子节点是否相同
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 100. 相同的树
上一篇
评论
