101. 对称二叉树

101. 对称二叉树

题目描述

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

如果一棵树沿着根节点的中心轴左右镜像后完全一致，那么它就是一棵对称二叉树。

示例 1

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

示例 2

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

约束

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

进阶

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

核心思路

这题的关键词不是“左右子树相等”，而是：

  • 左右子树互为镜像

“镜像”意味着比较的不是同一侧，而是：

  • 左树的左孩子，要和右树的右孩子比较
  • 左树的右孩子，要和右树的左孩子比较

所以这题本质上是在判断：

text
left 子树 和 right 子树 是否镜像对称

判断两棵树是否镜像，需要同时满足：

  1. 当前两个节点值相同
  2. 左边的左子树和右边的右子树镜像
  3. 左边的右子树和右边的左子树镜像

这题至少有两种常见做法：

  • 解法一：递归判断两棵树是否镜像（推荐）
  • 解法二：迭代 + 队列 / 数组成对比较

先理解：什么叫“对称”？

比如下面这棵树：

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

它是对称的。

因为：

  • 根节点左右两边值一样
  • 左边的 3 和右边的 3 对应
  • 左边的 4 和右边的 4 对应

而下面这棵树：

text
        1
      /   \
     2     2
      \     \
       3     3

就不是对称的。

因为虽然两边都有 3，但它们的位置不镜像：

  • 左边的 3 在右孩子位置
  • 右边的 3 也在右孩子位置

镜像要求应该是：

  • 一边在左，一边在右

所以这题一定要同时比较：

  • 节点值
  • 节点位置结构

解法一：递归判断镜像

这是最经典、最推荐掌握的做法。

思路拆解

定义一个函数：

text
isMirror(left, right)

表示：

  • 判断以 left 为根的树
  • 和以 right 为根的树
  • 是否互为镜像

那么递归规则就是：

情况 1：两个节点都为空

说明这一层对得上，返回 true。

情况 2：一个为空，一个不为空

说明结构不同，返回 false。

情况 3：两个节点值不同

说明不对称，返回 false。

情况 4：当前值相同

还要继续递归检查：

  • left.left 和 right.right
  • left.right 和 right.left

只有都成立，才是真正的镜像。

一步一步写出算法

第一步：定义递归函数

ts
const isMirror = (left: TreeNode | null, right: TreeNode | null): boolean => {
    ...
}

第二步：处理空节点情况

ts
if (left === null && right === null) {
    return true
}

if (left === null || right === null) {
    return false
}

第三步：处理节点值不同的情况

ts
if (left.val !== right.val) {
    return false
}

第四步：递归比较镜像位置

ts
return isMirror(left.left, right.right) && isMirror(left.right, right.left)

第五步：从根节点的左右子树开始比较

ts
return isMirror(root.left, root.right)

代码实现（TypeScript）

ts
class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0
        this.left = left ?? null
        this.right = right ?? null
    }
}

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

        if (left === null || right === null) {
            return false
        }

        if (left.val !== right.val) {
            return false
        }

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

    if (root === null) {
        return true
    }

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

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(h)

其中：

  • n 是节点总数
  • h 是树高
  • 递归栈最坏情况下可能到 O(n)，平衡树时大约是 O(log n)

这一解法的优缺点

优点：

  • 思路最自然
  • 代码最短
  • 面试里最推荐

缺点：

  • 需要对“镜像递归”有感觉
  • 递归写法依赖调用栈

解法二：迭代成对比较

这个做法本质上和递归一样，只是把“函数调用栈”改成了“手动维护待比较节点对”。

思路拆解

既然递归里每次都是比较一对节点：

  • (left, right)

那么迭代做法就可以用一个队列或数组，每次取出一对节点来比较。

每次拿出一对节点 (left, right) 后：

  1. 如果都为空，继续
  2. 如果一个为空，一个不为空，返回 false
  3. 如果值不同，返回 false
  4. 否则把它们的镜像孩子继续成对放进去：
    • left.left 和 right.right
    • left.right 和 right.left

如果最后所有节点对都成功匹配，就返回 true。

一步一步写出算法

第一步：初始化队列

把根节点左右孩子先放进去。

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

第二步：每次取出两个节点

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

第三步：处理空节点情况

ts
if (left === null && right === null) {
    continue
}

if (left === null || right === null) {
    return false
}

第四步：处理值不相等

ts
if (left.val !== right.val) {
    return false
}

第五步：按镜像顺序加入下一层

ts
queue.push(left.left)
queue.push(right.right)
queue.push(left.right)
queue.push(right.left)

最后如果没出错，说明整棵树对称。

代码实现（TypeScript）

ts
class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0
        this.left = left ?? null
        this.right = right ?? null
    }
}

function isSymmetric(root: TreeNode | null): boolean {
    if (root === null) {
        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 === null && right === null) {
            continue
        }

        if (left === null || right === null) {
            return false
        }

        if (left.val !== right.val) {
            return false
        }

        queue.push(left.left)
        queue.push(right.right)
        queue.push(left.right)
        queue.push(right.left)
    }

    return true
}

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

最坏情况下，队列中会存一层的很多节点。

这一解法的优缺点

优点：

  • 不依赖递归栈
  • 更容易看清“成对比较”的过程

缺点：

  • 代码稍长
  • 需要特别注意入队顺序必须是镜像顺序

两种解法对比

解法时间复杂度空间复杂度特点
递归判断镜像O(n)O(h)最自然，最推荐
迭代成对比较O(n)O(n)不用递归，更直观

如果你是第一次做这题，建议优先把递归写法彻底理解透。

手动模拟一遍递归解法

以这棵树为例：

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

第一步：比较根节点左右子树

调用：

text
isMirror(root.left, root.right)

也就是比较两个值为 2 的节点。

  • 值相同，继续往下比

第二步：比较外侧

比较：

text
left.left 和 right.right

也就是：

text
3 和 3

相同。

第三步：比较内侧

比较：

text
left.right 和 right.left

也就是：

text
4 和 4

也相同。

第四步：继续递归到空节点

再往下比较时，两边都会同时走到 null。

这说明每一层都能镜像对上，所以整棵树是对称的。

面试时最容易错的点

1. 比的是“镜像”，不是“相等”

很多人会下意识写成：

  • left.left 对 right.left
  • left.right 对 right.right

这是错的。

正确应该是：

  • left.left 对 right.right
  • left.right 对 right.left

2. 空节点也要比较

对称不仅看值，还看结构。

比如：

  • 一边有节点
  • 一边没有节点

即使值没机会比较，也已经不对称了。

3. 根节点为空时要返回 true

空树本身也是对称的。

4. 迭代法里入队顺序别乱

一定要按镜像顺序入队：

ts
left.left, right.right, left.right, right.left

否则比较逻辑会错。

一句话总结

这题的本质是：

判断左右子树是否互为镜像，而不是是否完全相同。

  • 想写标准解：用 递归判断镜像
  • 想不用递归：用 迭代成对比较

推荐你最后记住的标准写法

如果你准备刷题，建议优先记下面这个递归版本：

ts
class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0
        this.left = left ?? null
        this.right = right ?? null
    }
}

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

        if (left === null || right === null) {
            return false
        }

        if (left.val !== right.val) {
            return false
        }

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

    if (root === null) {
        return true
    }

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

因为这个版本：

  • 最贴合“镜像”的定义
  • 代码最短
  • 是这题公认的标准写法