LC101 · 对称二叉树 · 工程执行实验室
镜像安检门 · 折叠树
比较的是镜像位置，不是左右子树同方向比较。沿中轴线折叠后应完全重合： left.left 对 right.right，left.right 对 right.left。
核心 · 镜像交叉比较
比较的是镜像位置：left.left 对 right.right，left.right 对 right.left——沿中轴线折叠后应重合。
- · 对称不是左右一样，而是左右互为镜像。
- · 左树往左走，右树就要往右走。
- · 左树往右走，右树就要往左走。
- · 只比较 root.left.val 和 root.right.val 不够，必须一路比较所有镜像位置。
- a、b 都 nil → true
- 一空一非空 → false
- a.Val != b.Val → false
- mirror(a.L, b.R) && mirror(a.R, b.L)
- 1.mirror(a,b) 通过值检查后，压入 mirror(a.Left,b.Right) 与 mirror(a.Right,b.Left)。
- 2.子问题返回 true/false 后弹栈，用 && 合并给上一层。
- 3.一处 false 沿栈向上传递，isSymmetric 最终也 false。
题目输入：判断二叉树是否轴对称
给定一棵二叉树，判断是否轴对称。对称不是「左右子树长得差不多」，而是沿根的中轴线折叠后，左右子树互为镜像——镜像位置的值必须一一对应。
- 比较的是镜像位置：left.left 对 right.right，left.right 对 right.left——沿中轴线折叠后应重合。
- 对称不是左右一样，而是左右互为镜像。
- 左树往左走，右树就要往右走。
- 左树往右走，右树就要往左走。
- 只比较 root.left.val 和 root.right.val 不够，必须一路比较所有镜像位置。
比较的是镜像位置：left.left 对 right.right，left.right 对 right.left——沿中轴线折叠后应重合。
状态表 · mirror(a, b) / 调用栈
| a（左子树侧） | b（右子树侧） | 调用栈 | 返回值 | 动作 |
|---|---|---|---|---|
| a → 2（L） | b → 2（R） | [] | — | 读题输入 [1,2,2,3,4,4,3] |
递归栈 · 当前调用链
（空栈）
1func isSymmetric(root *TreeNode) bool {2 if root == nil {3 return true4 }5 return mirror(root.Left, root.Right)6}8func mirror(a, b *TreeNode) bool {9 if a == nil && b == nil {10 return true11 }12 if a == nil || b == nil {13 return false14 }15 if a.Val != b.Val {16 return false17 }18 return mirror(a.Left, b.Right) && mirror(a.Right, b.Left)19}
- 时间
- O(n)
- 空间
- O(h)
每个节点最多参与一次镜像配对比较，n 为节点总数。
h 为树高。平衡树约 O(log n)，最坏退化链表为 O(n)。递归版用系统调用栈保存暂停状态。最坏 O(n)
二叉树对称，当且仅当以根为轴左右子树互为镜像。isSymmetric 调用 mirror(root.Left, root.Right)；mirror(a,b) 中 a、b 都空返回 true，一空一非空 false，值不等 false，否则 return mirror(a.Left, b.Right) && mirror(a.Right, b.Left)。时间 O(n)，空间 O(h)，最坏 O(n)。
错误写法是 mirror(a.Left, b.Left) && mirror(a.Right, b.Right)。对称要交叉：a.Left 对 b.Right。
只比较 root.left.val 和 root.right.val 不够，必须一路比较所有镜像位置。
位置和值都要镜像匹配。[1,2,2,null,3,null,3] 中 left.left 为空、right.right 为 3，必须 false。
递归实现需要调用栈，空间是 O(h)，最坏退化链表时 O(n)。