深度优先遍历 DFS
复杂度
-
时间复杂度：
O(min(m,n))：- 其中 m 和 n 分别是两个二叉树的节点数；
- 对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树的节点数；
-
空间复杂度：
O(min(m,n))：- 其中 m 和 n 分别是两个二叉树的节点数；
- 空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数；
代码实现
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);
};
广度优先遍历 BFS
解题思路
首先判断两个二叉树是否为空，如果两个二叉树都不为空，则从两个二叉树的根节点开始广度优先搜索；
使用两个队列分别存储两个二叉树的节点。初始时将两个二叉树的根节点分别加入两个队列，每次从两个队列各取出一个节点，进行如下比较操作：
- 比较两个节点的值，如果两个节点的值不相同则两个二叉树一定不同；
- 如果两个节点的值相同，则判断两个节点的子节点是否为空，如果只有一个节点的左子节点为空，或者只有一个节点的右子节点为空，则两个二叉树的结构不同，因此两个二叉树一定不同；
- 如果两个节点的子节点的结构相同，则将两个节点的非空子节点分别加入两个队列，子节点加入队列时需要注意顺序，如果左右子节点都不为空，则先加入左子节点，后加入右子节点；
复杂度
-
时间复杂度：
O(min(m,n))：- 其中 m 和 n 分别是两个二叉树的节点数；
- 对两个二叉树同时进行广度优先搜索，只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树的节点数；
-
空间复杂度：
O(min(m,n))：- 其中 m 和 n 分别是两个二叉树的节点数；
- 空间复杂度取决于队列中的元素个数，队列中的元素个数不会超过较小的二叉树的节点数；
代码实现
var isSameTree = function (p, q) {
let queueP = [p];
let queueQ = [q];
while (queueP.length && queueQ.length) {
const nodeP = queueP.pop();
const nodeQ = queueQ.pop();
// 1. 节点为空，说明相同，跳出循环比较下一个节点
if (nodeP === null && nodeQ === null) continue;
// 2. 节点不相同的情况
if (nodeP === null || nodeQ === null) return false;
if (nodeP.val !== nodeQ.val) return false;
// 3. 当前节点相同，继续比较子节点
queueP.push(nodeP.left);
queueQ.push(nodeQ.left);
queueP.push(nodeP.right);
queueQ.push(nodeQ.right);
}
return true;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 101. 对称二叉树
上一篇
评论
