跳到主要内容

对称二叉树

问题​

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

示例：

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

输入：root = [1,2,2,null,3,null,3]
      1
     / \
    2   2
     \   \
      3   3
输出：false

来源：LeetCode 101. 对称二叉树

答案​

方法一：递归（推荐）​

核心思路：对称意味着左子树和右子树互为镜像。定义辅助函数 isMirror(left, right)，检查两棵树是否互为镜像：

  1. 两个节点都为空 → 对称
  2. 只有一个为空 → 不对称
  3. 值不相等 → 不对称
  4. 递归检查：left.left 与 right.right，left.right 与 right.left
isSymmetric.ts
function isSymmetric(root: TreeNode | null): boolean {
  if (!root) return true;
  return isMirror(root.left, root.right);
}

function isMirror(
  left: TreeNode | null,
  right: TreeNode | null
): boolean {
  // 两个都为空：对称
  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);
}

图解：

        1
       / \
      2   2       → isMirror(2, 2) ✓ val 相等
     / \ / \
    3  4 4  3     → isMirror(3, 3) ✓ 外侧
                  → isMirror(4, 4) ✓ 内侧

对称比较线：
      2   |   2
     / \  |  / \
    3  4  |  4  3
    ↕     |     ↕    外侧：左的左 vs 右的右
       ↕  |  ↕       内侧：左的右 vs 右的左
复杂度分析
  • 时间复杂度：O(n)O(n) — 每个节点最多访问一次
  • 空间复杂度：O(h)O(h) — 递归栈深度

方法二：BFS 迭代​

用队列成对地比较节点：

isSymmetricBFS.ts
function isSymmetric(root: TreeNode | null): boolean {
  if (!root) return true;

  const queue: Array<TreeNode | null> = [root.left, root.right];

  while (queue.length > 0) {
    const left = queue.shift()!;
    const right = queue.shift()!;

    if (!left && !right) continue;
    if (!left || !right) return false;
    if (left.val !== right.val) return false;

    // 成对入队：外侧对外侧，内侧对内侧
    queue.push(left.left, right.right);
    queue.push(left.right, right.left);
  }

  return true;
}

方法三：序列化比较（不推荐，仅了解）​

将左子树的中序遍历结果和右子树的镜像中序遍历结果比较：

isSymmetricSerialize.ts
function isSymmetric(root: TreeNode | null): boolean {
  if (!root) return true;

  function serialize(node: TreeNode | null, isLeft: boolean): string {
    if (!node) return '#';
    if (isLeft) {
      return `${node.val},${serialize(node.left, true)},${serialize(node.right, true)}`;
    } else {
      // 镜像：先右后左
      return `${node.val},${serialize(node.right, false)},${serialize(node.left, false)}`;
    }
  }

  return serialize(root.left, true) === serialize(root.right, false);
}
不推荐

需要构建字符串再比较，空间和时间都不如直接递归。

常见面试追问​

Q1: 如何将二叉树翻转为其镜像？(LeetCode 226)​

答案：

function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null;

  // 交换左右子树
  const temp = root.left;
  root.left = root.right;
  root.right = temp;

  invertTree(root.left);
  invertTree(root.right);

  return root;
}

Q2: 如何判断两棵树是否相同？(LeetCode 100)​

答案：对称二叉树的简化版——不需要镜像比较，直接对应位置比较：

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

Q3: 对称和相同的区别在代码上体现在哪？​

答案：

对称相同
比较 left.left 和 right.right比较 p.left 和 q.left
比较 left.right 和 right.left比较 p.right 和 q.right
镜像比较同方向比较

就一行代码的差别。

相关链接​