101. 对称二叉树

题目描述

给定一个二叉树的根节点 root，检查它是否是镜像对称的。

示例 1：

输入：root = [1,2,2,3,4,4,3]

输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]

输出：false

提示：

• 树中节点数目在范围 [1, 1000] 内
• -100 <= Node.val <= 100

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

出处：LeetCode

解法一：递归

思路

递归遍历二叉树，判断左右子树是否对称。

实现

function isSymmetric(root: TreeNode | null): boolean {
  if (root === null) {
    return true;
  }
  return isMirror(root.left, root.right);
}

function isMirror(left: TreeNode | null, right: TreeNode | null): boolean {
  if (left === null && right === null) {
    return true;
  }
  if (left === null || right === null) {
    return false;
  }
  return (
    left.val === right.val &&
    isMirror(left.left, right.right) &&
    isMirror(left.right, right.left)
  );
}

复杂度分析

• 时间复杂度：$O(n)$，其中 n 是二叉树的节点数。每个节点在递归中只被遍历一次。
• 空间复杂度：$O(n)$，其中 n 是二叉树的节点数。递归函数的调用栈的深度等于二叉树的高度，最坏情况下二叉树的高度等于节点数。

解法二：迭代

思路

使用队列进行迭代遍历，判断左右子树是否对称。

实现

function isSymmetric(root: TreeNode | null): boolean {
  if (root === null) {
    return true;
  }
  const queue: TreeNode[] = [root.left, root.right];
  while (queue.length > 0) {
    const left = queue.shift();
    const right = queue.shift();
    if (left === null && right === null) {
      continue;
    }
    if (left === null || right === null || left.val !== right.val) {
      return false;
    }
    queue.push(left.left, right.right);
    queue.push(left.right, right.left);
  }
  return true;
}

复杂度分析

• 时间复杂度：$O(n)$，其中 n 是二叉树的节点数。每个节点在广度优先搜索中只被遍历一次。
• 空间复杂度：$O(n)$，其中 n 是二叉树的节点数。空间复杂度取决于队列的大小，队列的大小不会超过二叉树的宽度，最坏情况下二叉树的宽度等于节点数。