[Leetcode 101] 对称二叉树

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一个二叉树的根节点root,检查它是否轴对称。
 
示例 1:
notion image
 
示例 2:
notion image
 

解法一:递归版DFS(推荐)

一棵树要对称,就是左子树和右子树互为镜像,也就是:左的左 ≈ 右的右、左的右 ≈ 右的左,并且对应节点的值要相等。所以只需要写一个 mirror(L, R)判断以 LR 为根的两棵子树是不是镜像。
镜像是一个结构+值 双约束的递归定义:
  • 结构:L 的左对 R 的右,L 的右对 R 的左;
  • 值:对应节点值相等。
递归下去,只要每一层两对孩子都匹配,就能保证整棵子树匹配。
复杂度
  • 时间:O(n),每个节点最多被比较一次。
  • 空间:O(h),递归栈高度,最坏退化链为 O(n),平衡树约 O(log n)

解法二:BFS

把“递归比对子树”改成显式队列做广度搜索。
每次从队列里成对取出两个节点(本该是镜像的一对),做同样的相等判断;如果相等,就把它们的孩子按镜像顺序成对压回队列:
  • L.leftR.right
  • L.rightR.left
这就是把“镜像递归”的调用顺序,显式排成“待检查的节点对”序列。只要队列里所有成对检查都通过,树就镜像;一旦某对不通过,立即失败。
复杂度
  • 时间:O(n),每个节点至多入队出队一次(成对)。
  • 空间:O(w),队列最大宽度 w,最坏可到 O(n)

解法三:迭代版DFS

和队列思路一样,只是容器换成了,把“镜像对子”按 DFS 处理。
逻辑上是一样的:弹出一对 → 判空/判值 → 压入两对孩子(镜像顺序)。
DFS/BFS 本质差别只是遍历顺序,我们不要求“层序性质”,只要求“每对镜像节点都一致”,所以 DFS 同样可以。
复杂度
  • 时间:O(n)
  • 空间:O(h)O(n),取决于栈深(树形状)。

解法四:BFS + 回文校验

对称不仅是“值相等”,还有“结构对称”。
我们可以“按层检查”:一棵对称树,每一层从左到右的“值序列”(把空孩子也用占位符记下来),应该是个回文
None 占位把结构也序列化下来,层层回文就能同时保证这两点。
 
于是我们层序遍历,每层收集:
  • 非空节点就收它的值;
  • 空节点用一个特定的占位(比如 None),并且必须None 的孩子也视作 None 扔进下一层(否则结构信息会丢失)。
然后检查这一层是否回文即可。
复杂度
  • 时间:O(n)(每个真实节点处理一次;注意上面去尾部占位符,避免无穷膨胀)
  • 空间:最坏 O(n)(层宽 + 占位)
上一篇
[Leetcode 92] 反转链表II
下一篇
[Leetcode 105] 从前序与中序遍历序列构造二叉树