415 lines
13 KiB
Markdown
415 lines
13 KiB
Markdown
---
|
||
tags: ["LeetCode", "二叉树", "深度优先搜索", "广度优先搜索", "递归", "迭代", "简单"]
|
||
create time: 2026-05-17 11:00
|
||
---
|
||
|
||
# 39-对称二叉树
|
||
|
||
## 题面
|
||
|
||
给你一个二叉树的根节点 `root`，检查它是否**轴对称**。
|
||
|
||
> [!question] 💡 什么是「轴对称」？
|
||
> 一棵二叉树轴对称意味着：如果沿根节点画一条垂直中线，**左半树是右半树的镜像翻转**。
|
||
>
|
||
> > [!note] 🪞 直观理解
|
||
> > - 根节点永远对称（自己是自己的镜像）
|
||
> > - 左子树的左孩子 = 右子树的右孩子（值相等）
|
||
> > - 左子树的右孩子 = 右子树的左孩子（值相等）
|
||
> > - 上述规则**递归地**适用于所有层
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入：root = [1,2,2,3,4,4,3]
|
||
输出：true
|
||
1 ← 根节点
|
||
/ \
|
||
2 2 ← 两层对称 ✅
|
||
/ \ / \
|
||
3 4 4 3 ← 三层对称 ✅
|
||
```
|
||
|
||
**示例 2：**
|
||
|
||
```
|
||
输入：root = [1,2,2,null,3,null,3]
|
||
输出：false
|
||
1 ← 根节点
|
||
/ \
|
||
2 2 ← 二层对称 ✅
|
||
\ \
|
||
3 3 ← 三层不对称！左边是左孩子，右边是右孩子 ❌
|
||
```
|
||
|
||
> [!warning] ⚠️ 关键陷阱
|
||
> 示例 2 看起来两棵子树的「形状和值」完全一样，但**对称比较的不是两个子树各自相同，而是它们的镜像关系**。左子树的空位对应右子树的位置，不能简单地判断"两棵子树相等"。
|
||
|
||
**约束：**
|
||
|
||
- 树中节点数目在范围 `[1, 1000]` 内
|
||
- `-100 <= Node.val <= 100`
|
||
|
||
**进阶：** 你可以运用递归和迭代两种方法解决这个问题吗？
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
### 方法一：深度优先搜索 DFS（递归）⭐⭐
|
||
|
||
#### 核心洞察
|
||
|
||
> [!question] 🤔 思考
|
||
> 我们已经知道如何判断两棵树是否完全相等——同时遍历、逐节点比较。但「对称」不是比较两棵相同的树，而是比较两棵树是否为**镜像**。这两者有什么区别？
|
||
|
||
关键区别在于遍历顺序：
|
||
|
||
| 比较方式 | 左子树遍历 | 右子树遍历 |
|
||
|---------|----------|----------|
|
||
| **相等比较** | 先左后右 | 先左后右 |
|
||
| **镜像比较** | 先左后右 | **先右后左** |
|
||
|
||
所以判断对称的本质是：编写一个辅助函数 `isMirror(left, right)`，同时遍历两棵子树，但方向相反：
|
||
|
||
```
|
||
isMirror(left, right):
|
||
// 两个都是 nil → 对称
|
||
// 只有一个 nil → 不对称
|
||
// 值不等 → 不对称
|
||
// 值相等 → 交叉比较:
|
||
// isMirror(left.left, right.right) && isMirror(left.right, right.left)
|
||
```
|
||
|
||
#### 递归三要素
|
||
|
||
| 要素 | 内容 |
|
||
|------|------|
|
||
| **终止条件** | ① 双 nil → true；② 单 nil → false；③ 值不等 → false |
|
||
| **递归表达式** | `left.left` 与 `right.right` 镜像 + `left.right` 与 `right.left` 镜像 |
|
||
| **返回值** | 布尔值，表示两节点是否互为镜像 |
|
||
|
||
#### 执行流程图解
|
||
|
||
以对称树 `[] (1,2,2,3,4,4,3)` 为例，展示镜像比较的配对路径：
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
S["isMirror(2L, 2R)\n值相等(2=2)"] --> P1["交叉对1:\nisMirror(3L, 3R)\n值相等(3=3)\n✅ true"]
|
||
S --> P2["交叉对2:\nisMirror(4L, 4R)\n值相等(4=4)\n✅ true"]
|
||
P1 --> COMBINE["2L↔2R 两边都✅\n→ true"]
|
||
P2 --> COMBINE
|
||
COMBINE --> ROOT["isMirror(root.Left, root.Right)\n整棵树对称 ✅🎉"]
|
||
|
||
style ROOT fill:#d4edda,stroke:#28a745,stroke-width:3px
|
||
style COMBINE fill:#d4edda,stroke:#28a745
|
||
style P1 fill:#cce5ff,stroke:#004085
|
||
style P2 fill:#cce5ff,stroke:#004085
|
||
|
||
linkStyle 0,1,2 stroke:#28a745,stroke-width:2px
|
||
```
|
||
|
||
再看不对称的 `[] (1,2,2,null,3,null,3)`：
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
S["isMirror(2L, 2R)\n值相等(2=2)"] --> P1["交叉对1:\nisMirror(nil, 3R)\n左侧nil右侧非nil\n→ false ❌"]
|
||
S --> P2["交叉对2:\nisMirror(4L, nil)\n左侧非nil右侧nil\n→ false ❌"]
|
||
P1 --> FAIL["2L↔2R 至少一边❌\n→ false"]
|
||
P2 --> FAIL
|
||
FAIL --> ROOT["isMirror(root)\n左子树 != 右子树镜像\n→ 整棵不对称 ❌"]
|
||
|
||
style FAIL fill:#f8d7da,stroke:#721c24,stroke-width:2px
|
||
style ROOT fill:#f8d7da,stroke:#721c24,stroke-width:3px
|
||
style P1 fill:#fff3cd,stroke:#856404
|
||
style P2 fill:#fff3cd,stroke:#856404
|
||
```
|
||
|
||
#### 为什么是「交叉」而不是「平行」？
|
||
|
||
> [!info] 🧠 对称 vs 相等的本质差异
|
||
>
|
||
> ```
|
||
> 判断两棵树 A 和 B 是否「相等」:
|
||
> compare(A.left, B.left) AND compare(A.right, B.right)
|
||
> ↑ ↑
|
||
> 左 ↔ 左 右 ↔ 右
|
||
>
|
||
> 判断两棵树 A 和 B 是否「对称/镜像」:
|
||
> mirror(A.left, B.right) AND mirror(A.right, B.left)
|
||
> ↑ ↑ ↑ ↑
|
||
> A的左 ↔ B的右 A的右 ↔ B的左
|
||
> └── 镜面反射方向 ──┘
|
||
> ```
|
||
>
|
||
> 这就是为什么「相等」用 `compare(left, left) + compare(right, right)`，而「对称」必须用 `mirror(left, right) + mirror(right, left)`——**方向交叉**是关键！
|
||
|
||
### 方法二：广度优先搜索 BFS（队列迭代）⭐
|
||
|
||
#### 核心思想
|
||
|
||
既然递归用栈隐式保存了待比较的节点对，那么 BFS 可以用显式队列来存储待比较的节点对：**每次从队列取出两个节点，比较它们是否镜像，再将它们的镜像孩子对入队。**
|
||
|
||
```
|
||
queue = [(root.left, root.right)]
|
||
|
||
while queue 非空:
|
||
left, right = pop(queue)
|
||
|
||
if both nil: continue
|
||
if only one nil: return false
|
||
if values differ: return false
|
||
|
||
// 将镜像孩子对按交叉顺序入队
|
||
push(queue, (left.left, right.right)) // 外侧对
|
||
push(queue, (left.right, right.left)) // 内侧对
|
||
|
||
return true
|
||
```
|
||
|
||
#### 执行流程图
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
A["初始: [(2L, 2R)]"] -->|"比较: 2=2 ✅"| B["入队: (3L,3R), (4L,4R)"]
|
||
B -->|"比较: 3=3 ✅"| C["入队: (nil,nil), (nil,nil)"]
|
||
C -->|"跳过双nil"| D["继续取 (4L,4R)"]
|
||
D -->|"比较: 4=4 ✅"| E["入队: (nil,nil), (nil,nil)"]
|
||
E -->|"全部完成"| F["队列为空\n返回 true ✅"]
|
||
|
||
style F fill:#d4edda,stroke:#28a745,stroke-width:3px
|
||
style B fill:#e3f2fd,stroke:#004085
|
||
style D fill:#e3f2fd,stroke:#004085
|
||
```
|
||
|
||
### 方法三：深度优先搜索 DFS（栈迭代）⭐
|
||
|
||
除了 BFS 用队列，DFS 也可以用显式栈模拟递归过程。
|
||
|
||
> [!comparison] ⚖️ 三种写法对比
|
||
> | 维度 | DFS 递归 | BFS 队列迭代 | DFS 栈迭代 |
|
||
> |------|---------|-------------|-----------|
|
||
> | 代码简洁度 | ⭐⭐⭐ 仅需 6 行 | ⭐⭐ 需维护队列 | ⭐⭐ 需维护栈 |
|
||
> | 空间复杂度 | O(h) 递归栈 | O(n) 队列最多存一层节点对 | O(h) 栈深度 |
|
||
> | 比较顺序 | 前序（当前对→外侧→内侧） | 逐层（自顶向下） | 前序（自定义） |
|
||
> | 面试推荐度 | **首选** | 直观易懂 | 展示底层理解 |
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
### 递归伪代码
|
||
|
||
```
|
||
func isMirror(left, right *TreeNode) bool:
|
||
// 终止条件①: 两个都为空 → 对称
|
||
if left == nil and right == nil:
|
||
return true
|
||
|
||
// 终止条件②: 只有一个为空 → 不对称
|
||
if left == nil or right == nil:
|
||
return false
|
||
|
||
// 终止条件③: 值不等 → 不对称
|
||
if left.Val != right.Val:
|
||
return false
|
||
|
||
// 递归: 交叉比较（外侧对外侧，内侧对内侧）
|
||
return isMirror(left.Left, right.Right) and isMirror(left.Right, right.Left)
|
||
|
||
func isSymmetric(root *TreeNode) bool:
|
||
return isMirror(root.Left, root.Right)
|
||
```
|
||
|
||
### BFS 迭代伪代码
|
||
|
||
```
|
||
if root == nil: return true
|
||
|
||
queue = [(root.Left, root.Right)]
|
||
|
||
while len(queue) > 0:
|
||
left, right = pop(queue)
|
||
|
||
if left == nil and right == nil: continue
|
||
if left == nil or right == nil: return false
|
||
if left.Val != right.Val: return false
|
||
|
||
push(queue, (left.Left, right.Right))
|
||
push(queue, (left.Right, right.Left))
|
||
|
||
return true
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 「对称」和「相等」是一组好基友
|
||
> LeetCode 100. 相同的树判断两棵树是否完全相等，LeetCode 101. 对称二叉树判断两棵树是否互为镜像。两者代码结构高度相似，唯一的区别就是**参数遍历的方向**——相等是 `(左,左)+(右,右)`，对称是`(左,右)+(右,左)`。对比练习效果极佳。
|
||
|
||
> [!tip] 🔑 Go 多值赋值的优雅应用
|
||
> 虽然这道题不需要交换操作，但在类似的树问题中，Go 的多值赋值能让你避开临时变量。更重要的是，递归的两个子调用写在 `and` 两侧，Go 会在第一个结果为 false 时短路——天然优化。
|
||
|
||
> [!info] 📊 复杂度速查
|
||
> | 方法 | 时间复杂度 | 空间复杂度 |
|
||
> |------|-----------|-----------|
|
||
> | DFS 递归 | **O(n)** — 每个节点对访问一次 | **O(h)** — h 为树高，最坏 O(n)（链状），平均 O(log n)（平衡树） |
|
||
> | BFS 队列迭代 | **O(n)** — 每对节点入队出队各一次 | **O(n)** — 最坏情况下队列可能存 O(n)/2 个节点对 |
|
||
> | DFS 栈迭代 | **O(n)** | **O(h)** |
|
||
|
||
> [!warning] ⚠️ 常见错误：忘记处理双 nil 情况
|
||
> 有些人在写递归时只写了「左 nil 或右 nil 返回 false」，这会误判一对双 nil 叶子。双 nil 应该返回 true——因为它们都是空节点，自然是对称的。
|
||
|
||
> [!note] 🧩 延伸思考
|
||
> - **相同的树**（LeetCode 100）：比较思路几乎一致，只是参数方向不交叉
|
||
> - **二叉树的最大深度**（LeetCode 104）：对称树可以看作是求"左子树深度 == 右子树深度且结构镜像"
|
||
> - **N 叉树的对称性**：扩展到 N 叉树时，需要判断第 i 个孩子和第 (n-1-i) 个孩子是否互为镜像
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
### DFS 递归法（推荐）⭐⭐
|
||
|
||
```go
|
||
/**
|
||
* Definition for a binary tree node.
|
||
* type TreeNode struct {
|
||
* Val int
|
||
* Left *TreeNode
|
||
* Right *TreeNode
|
||
* }
|
||
*/
|
||
func isSymmetric(root *TreeNode) bool {
|
||
// 空树对称
|
||
return isMirror(root, root)
|
||
}
|
||
|
||
// isMirror 判断两棵树是否互为镜像
|
||
func isMirror(left, right *TreeNode) bool {
|
||
// 两个节点都为空 → 对称
|
||
if left == nil && right == nil {
|
||
return true
|
||
}
|
||
// 只有一个为空 → 不对称
|
||
if left == nil || right == nil {
|
||
return false
|
||
}
|
||
// 值不相等 → 不对称
|
||
if left.Val != right.Val {
|
||
return false
|
||
}
|
||
// 交叉比较：外侧对外侧，内侧对内侧
|
||
return isMirror(left.Left, right.Right) && isMirror(left.Right, right.Left)
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> 这是 LeetCode 第 101 题，通过率约 59%。代码虽短，但包含了二叉树递归的经典范式——**定义函数语义 → 列出终止条件 → 写出递归表达式**。注意这里巧妙地把 `root` 作为两棵树的根同时传入 `isMirror(root, root)`，让根节点的左右子树成为首次比较的对象。
|
||
|
||
### BFS 队列迭代法（参考）⭐
|
||
|
||
```go
|
||
/**
|
||
* Definition for a binary tree node.
|
||
* type TreeNode struct {
|
||
* Val int
|
||
* Left *TreeNode
|
||
* Right *TreeNode
|
||
* }
|
||
*/
|
||
func isSymmetric(root *TreeNode) bool {
|
||
if root == nil {
|
||
return true
|
||
}
|
||
|
||
// 使用切片模拟队列，存储待比较的节点对
|
||
type pair struct {
|
||
left, right *TreeNode
|
||
}
|
||
queue := []pair{{root.Left, root.Right}}
|
||
|
||
for len(queue) > 0 {
|
||
// 出队
|
||
pair := queue[0]
|
||
queue = queue[1:]
|
||
left, right := pair.left, pair.right
|
||
|
||
// 两个都为空 → 继续下一对
|
||
if left == nil && right == nil {
|
||
continue
|
||
}
|
||
// 只有一个为空 → 不对称
|
||
if left == nil || right == nil {
|
||
return false
|
||
}
|
||
// 值不等 → 不对称
|
||
if left.Val != right.Val {
|
||
return false
|
||
}
|
||
|
||
// 将镜像孩子对按交叉顺序入队
|
||
queue = append(queue, pair{left.Left, right.Right}) // 外侧对
|
||
queue = append(queue, pair{left.Right, right.Left}) // 内侧对
|
||
}
|
||
|
||
return true
|
||
}
|
||
```
|
||
|
||
> [!note] 🐹 设计选择说明
|
||
> 这里使用了自定义 `pair` 结构体来存储节点对，相比 `[][]*TreeNode` 或扁平化两个队列的方式更直观。Go 的匿名结构体语法让这种配对变得简洁——在 Python 中直接用元组 `(left, right)`，在 Java 中可能需要自定义 Pair 类。
|
||
|
||
### DFS 栈迭代法（参考）⭐
|
||
|
||
```go
|
||
/**
|
||
* Definition for a binary tree node.
|
||
* type TreeNode struct {
|
||
* Val int
|
||
* Left *TreeNode
|
||
* Right *TreeNode
|
||
* }
|
||
*/
|
||
func isSymmetric(root *TreeNode) bool {
|
||
if root == nil {
|
||
return true
|
||
}
|
||
|
||
// 用切片模拟栈，存储待比较的节点对
|
||
type pair struct {
|
||
left, right *TreeNode
|
||
}
|
||
stack := []pair{{root.Left, root.Right}}
|
||
|
||
for len(stack) > 0 {
|
||
// 弹栈
|
||
n := len(stack) - 1
|
||
pair := stack[n]
|
||
stack = stack[:n]
|
||
left, right := pair.left, pair.right
|
||
|
||
if left == nil && right == nil {
|
||
continue
|
||
}
|
||
if left == nil || right == nil {
|
||
return false
|
||
}
|
||
if left.Val != right.Val {
|
||
return false
|
||
}
|
||
|
||
// 注意：栈是 LIFO，所以要逆序入栈才能保证比较顺序
|
||
// 与递归的前序逻辑一致：先处理内侧再处理外侧
|
||
stack = append(stack, pair{left.Right, right.Left}) // 内侧对先入
|
||
stack = append(stack, pair{left.Left, right.Right}) // 外侧对后入
|
||
}
|
||
|
||
return true
|
||
}
|
||
```
|
||
|
||
> [!tip] 🐹 BFS vs DFS 迭代的关键区别
|
||
> BFS 用**队列**（FIFO）——先入队的先被弹出，实现逐层比较；DFS 迭代用**栈**（LIFO）——后入栈的先被弹出。在 DFS 迭代中，如果要模拟递归的「先处理外侧再处理内侧」的顺序，就必须把内侧对**先入栈**，这样它反而会被**后弹出**——这体现了栈的逆序特性。
|