Javajava算法
LeetCode 101. 对称二叉树：递归与迭代解法详解
本文针对 LeetCode 101 对称二叉树问题，提供了递归和迭代两种解决方案。核心思想是判断左子树与右子树是否互为镜像。递归法通过比较节点值与结构实现，迭代法利用队列逐层验证。文章分析了时间复杂度 O(n) 与空间复杂度，并给出了 Java 和 Go 的代码实现示例，适合树结构遍历与递归思维训练。
本文针对 LeetCode 101 对称二叉树问题，提供了递归和迭代两种解决方案。核心思想是判断左子树与右子树是否互为镜像。递归法通过比较节点值与结构实现，迭代法利用队列逐层验证。文章分析了时间复杂度 O(n) 与空间复杂度，并给出了 Java 和 Go 的代码实现示例，适合树结构遍历与递归思维训练。
LeetCode 101. 对称二叉树
给你一个二叉树的根节点 root，检查它是否轴对称。
输入：root = [1,2,2,3,4,4,3]
输出：true
输入：root = [1,2,2,null,3,null,3]
输出：false
[1, 1000] 内-100 <= Node.val <= 100核心思想：一棵二叉树是对称的，当且仅当它的左子树和右子树互为镜像。
isMirror(left, right) 判断两个子树是否互为镜像isMirror(left, right) = (left == null && right == null) ||
(left != null && right != null && left.val == right.val &&
isMirror(left.left, right.right) &&
isMirror(left.right, right.left))
核心思想：使用队列模拟递归过程，逐层比较对称位置的节点。
left.left 和 right.rightleft.right 和 right.left| 方法 | 时间复杂度 | 空间复杂度 | 代码简洁度 | 理解难度 |
|---|---|---|---|---|
| 递归法 | O(n) | O(h) | ⭐⭐⭐⭐⭐ | ⭐⭐ |
| 迭代法 | O(n) | O(n) | ⭐⭐⭐ | ⭐⭐⭐ |
h 为树的高度，n 为节点总数
// 方法一：递归法
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode left, TreeNode right) {
// 两个都为空，对称
if (left == null && right == null) {
return true;
}
// 一个为空，一个不为空，不对称
if (left == null || right == null) {
return false;
}
// 值不相等，不对称
if (left.val != right.val) {
return false;
}
// 递归检查：左子树的左孩子 vs 右子树的右孩子
// 左子树的右孩子 vs 右子树的左孩子
return isMirror(left.left, right.right) && isMirror(left.right, right.left);
}
}
// 方法二：迭代法
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()) {
TreeNode left = queue.poll();
TreeNode right = queue.poll();
// 两个都为空，继续
if (left == null && right == null) {
continue;
}
// 一个为空或值不等
if (left == null || right == null || left.val != right.val) {
return false;
}
// 按对称顺序加入队列
queue.offer(left.left);
queue.offer(right.right);
queue.offer(left.right);
queue.offer(right.left);
}
return true;
}
}
// 方法一：递归法
func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}
return isMirror(root.Left, root.Right)
}
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)
}
// 方法二：迭代法
func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}
queue := []*TreeNode{root.Left, root.Right}
for len(queue) > 0 {
left := queue[0]
right := queue[1]
queue = queue[2:]
// 两个都为空，继续
if left == nil && right == nil {
continue
}
// 一个为空或值不等
if left == nil || right == nil || left.Val != right.Val {
return false
}
// 按对称顺序加入队列
queue = append(queue, left.Left, right.Right, left.Right, right.Left)
}
return true
}
[1,2,2,3,4,4,3] 1
/ \
2 2
/ \ / \
3 4 4 3
递归调用过程：
isMirror(2, 2) → 值相等isMirror(3, 3) → 值相等，且都为叶子节点 → trueisMirror(4, 4) → 值相等，且都为叶子节点 → true[1,2,2,null,3,null,3] 1
/ \
2 2
\ \
3 3
递归调用过程：
isMirror(2, 2) → 值相等isMirror(null, null) → true（左子树的左 vs 右子树的右）isMirror(3, 3) → 值相等left.left = null, right.right = nullleft.right = 3, right.left = null → 返回 false注意：示例 2 的关键在于右子树的左孩子是 null，而左子树的右孩子是 3
如果算法返回 true，那么二叉树一定是对称的。
如果二叉树是对称的，那么算法一定返回 true。
left.left ↔ right.right，left.right ↔ right.left优先使用递归法，因为：
这个问题是理解二叉树递归操作的经典例题，掌握后可以轻松应对类似的树结构比较问题。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online