#101. 对称二叉树

LeetCode 原题链接

#题目描述

判断一棵二叉树是否关于根节点轴对称。

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

#题型判断

对称不是分别判断左右子树是否相同，而是成对比较镜像位置：

• 左子树的左孩子对应右子树的右孩子。
• 左子树的右孩子对应右子树的左孩子。

可以把根节点看成一条对称轴。左边越靠外的位置，对应的是右边越靠外的位置；左边靠内的位置，对应的是右边靠内的位置。

1
      /   \
     2     2
    / \   / \
   3   4 4   3

外侧：左子树的 3 对应右子树的 3
内侧：左子树的 4 对应右子树的 4

递归最直接；也可以把成对节点放进队列做 BFS。

#核心思路

定义 isMirror(left, right)：

isMirror(left, right) 判断的是：以 left 为根的子树，和以 right 为根的子树，是否互为镜像。

1. 两个节点都为空，当前镜像位置相同。
2. 只有一个为空，或者值不同，不对称。
3. 继续交叉比较两组外侧、内侧孩子。

交叉比较对应的是：

• left.left 和 right.right：两棵子树的外侧。
• left.right 和 right.left：两棵子树的内侧。

只要外侧和内侧都对称，当前这两棵子树才是镜像。

#代码实现

var isSymmetric = function (root) {
  if (!root) return true;

  const isMirror = (left, right) => {
    if (!left && !right) return true;
    if (!left || !right) return false;
    if (left.val !== right.val) return false;

    return (
      isMirror(left.left, right.right) &&
      isMirror(left.right, right.left)
    );
  };

  return isMirror(root.left, root.right);
};

#复杂度分析

• 时间复杂度：O(n)，最坏需要比较所有节点。
• 空间复杂度：O(h)，递归栈深度为树高 h；极度倾斜时为 O(n)。

#边界与易错点

• 空树是对称的。
• 节点值相同但结构不同，仍然不对称。
• 不要比较 left.left 和 right.left，镜像比较必须交叉。
• 树可能很深时，可改用显式队列避免递归栈溢出。
• 对称比较的是结构和值都相同，不能只比较每一层的节点值是否回文。