广度优先遍历 BFS
解题思路
使用 层序遍历 进行遍历，队列里面会放置二叉树每一层的节点；
向队列中放入节点的时候，按照 leftNode.left、rightNode.right、leftNode.right、rightNode.left 的顺序放入；
不对称的情况：
- 任意一个左右节点为空，则不对称；
- 左右节点不为空但值不相等，则不对称；
复杂度
-
时间复杂度：
O(N)，其中 N 为二叉树的节点数量； -
空间复杂度：
O(N)，队列中元素的个数不超过 N 个；
代码实现
var isSymmetric = function (root) {
if (root === null) return true;
let queue = [root.left, root.right];
while (queue.length) {
let leftNode = queue.shift(); // 左节点
let rightNode = queue.shift(); // 右节点
if (leftNode === null && rightNode === null) continue;
if (leftNode === null || rightNode === null || leftNode.val !== rightNode.val) return false;
queue.push(leftNode.left); // 左节点左孩子入队
queue.push(rightNode.right); // 右节点右孩子入队
queue.push(leftNode.right); // 左节点右孩子入队
queue.push(rightNode.left); // 右节点左孩子入队
}
return true;
};
深度优先遍历 DFS
解题思路
如果同时满足下面的条件，两个树互为镜像：
- 它们的两个根结点具有相同的值；
- 每个树的右子树都与另一个树的左子树镜像对称；
递归判断左右两颗子树是否是镜像的；
L.left.val === R.right.val：即 L 的 左子节点 和 R 的 右子节点 对称；L.right.val === R.left.val：即 L 的 右子节点 和 R 的 左子节点 对称；
复杂度
-
时间复杂度：
O(N)，其中 N 为二叉树的节点数量； -
空间复杂度：
O(n)，为迭代过程中栈的开销，平均情况下为O(logn)，最坏情况下树呈现链状，为O(n)；
代码实现
var isSymmetric = function (root) {
return travese(root.left, root.right);
};
const travese = (root1, root2) => {
if (root1 === null && root2 === null) return true;
if (root1 === null || root2 === null) return false;
if (root1.val === root2.val) {
return travese(root1.left, root2.right) && travese(root1.right, root2.left);
}
return false;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 226. 翻转二叉树
上一篇
评论
