【LeetCode刷题日记】面试官最爱的二叉树题：对称二叉树——递归+BFS双解法一网打尽

🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

摘要：

本文探讨了判断二叉树是否对称的两种解法。递归法通过比较左右子树是否互为镜像，满足三个条件：节点值相等、左子树与右子树镜像、右子树与左子树镜像。迭代法使用队列进行广度优先搜索，成对比较节点并检查对称性。两种方法均需处理空节点情况，确保结构对称性和数值一致性。代码示例展示了递归和迭代的具体实现，通过逐层比较节点值及其子节点关系来判断对称性。该问题考察了对二叉树遍历和镜像概念的理解。

题目背景：101.对称二叉树

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

示例 1：

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

示例 2：

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

提示：

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

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

题目分析：

其实我们在LeetCode刷题的时候，不能仅仅是看题目的难度，如果看到标的是简单，可能会产生忽视心理，同时如果没思路，也很会影响心态，我们要保持平常心，认真的对待每一题，往往有的简单题也蕴含着很深刻的知识。

首先我们来看这个题目。要我们来判断这个二叉树是否对称，我们就要想，怎么判断它是否对称呢，我们观察一下题目中给出的示例，对称其实就是左右是一个镜像，左子树等于右子树，简单的说我们只需要完成下列判断：

判断二叉树是否对称 = 判断左右子树是否互为镜像

两个树互为镜像的条件是：

1. 两个根节点的值相同

2. 树1的左子树 与 树2的右子树 互为镜像

3. 树1的右子树 与 树2的左子树 互为镜像

1 / \ 2 2 / \ / \ 3 4 4 3 判断流程： 比较节点(2, 2)：值相等 ✓ ├── 比较(2的左=3, 2的右=3)：3==3 ✓ │ ├── 比较(3的左=null, 3的右=null)：null==null ✓ │ └── 比较(3的右=null, 3的左=null)：null==null ✓ └── 比较(2的右=4, 2的左=4)：4==4 ✓ ├── 比较(4的左=null, 4的右=null)：null==null ✓ └── 比较(4的右=null, 4的左=null)：null==null ✓

---

我们下面用两种方法来解决

递归法（DFS）：

首先我们照旧判断二叉树的根节点是否为null，如果为null直接返回。

然后我们判断是否为镜像：

1. 确定递归函数的参数和返回值

因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。

返回值自然是bool类型。

1. 确定终止条件

要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。

节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）

• 左节点为空，右节点不为空，不对称，return false
• 左不为空，右为空，不对称 return false
• 左右都为空，对称，返回true

此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：

• 左右都不为空，比较节点数值，不相同就return false

此时左右节点不为空，且数值也不相同的情况我们也处理了。

1. 确定单层递归的逻辑

此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。

• 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
• 比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
• 如果左右都对称就返回true ，有一侧不对称就返回false 。

java

return (t1.val == t2.val) // 条件1：值相等 && isMirror(t1.left, t2.right) // 条件2：左的左 与 右的右 互为镜像 && isMirror(t1.right, t2.left); // 条件3：左的右 与 右的左 互为镜像

这三个条件用&&连接，缺一不可

代码行	判断什么	为什么重要
if (t1 == null && t2 == null) return true;	两个都是空节点	基础情况，递归的终点
if (t1 == null || t2 == null) return false;	其中一个为空	结构不对称（一个有空，另一个没有）
(t1.val == t2.val)	两个节点的值相等	数值不对称也不行
isMirror(t1.left, t2.right)	外层与内层对称	镜像的核心要求
isMirror(t1.right, t2.left)	内层与外层对称	镜像的核心要求

图解执行过程

以对称树为例：

text

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

调用isMirror(2, 2)：

java

// 第一层：两个节点都不为null 返回: (2 == 2) // ✓ 值相等 && isMirror(2.left=3, 2.right=3) // 递归进入第二层左 && isMirror(2.right=4, 2.left=4) // 递归进入第二层右

进入isMirror(3, 3)：

java

// 第二层左：两个节点都不为null 返回: (3 == 3) // ✓ 值相等 && isMirror(3.left=null, 3.right=null) // 递归 && isMirror(3.right=null, 3.left=null) // 递归

进入isMirror(null, null)：

java

// 第三层：两个都是null 返回: true // ✅ t1==null && t2==null

所以isMirror(3, 3)完整返回：

java

true && true && true = true

同样isMirror(4, 4)也会返回true。

最终结果：

java

true && true && true = true

迭代法（BFS）：

迭代法的思路也是一样，但我们这里使用的是队列来操作，我们创建一个队列，然后把根节点的左右节点入队，然后我们进入while循环，把这两个节点取出

然后我们进行条件判断，首先是判断两个左右节点时候都为null，如果都为null，我们直接continue，这里为什么不是直接返回true呢

java

if (t1 == null && t2 == null) continue;

意思是：

• 这一对节点对称（都是空）

• 不需要再检查它们的子节点（因为空节点没有子节点）

• 继续检查队列中其他待比较的对

我们刚进入循环的时候肯定不是null，因为进入while循环的条件就是队列非空，防止的是后面的节点的null值。

以这棵树为例：

text

1 / \ 2 2 \ \ 3 3

第1轮：处理 (2, 2)

java

t1.left = null (2没有左孩子) t2.right = 3 (2的右孩子是3) t1.right = 3 (2的右孩子是3) t2.left = null (2没有左孩子) 入队顺序：[null, 3, 3, null] ↑ ↑ ↑ ↑ │ │ │ └── 第2对的右 │ │ └────── 第2对的左 │ └───────── 第1对的右 └────────────── 第1对的左

第2轮：取出 (null, 3)

• 这时t1 == null，t2 != null

• 发现不对称 → 返回 false

如果没有 null 判断，代码会在t1.val时抛出空指针异常

所以 null 判断的作用

判断	作用
if (t1 == null && t2 == null) continue;	两个都是 null，说明这对节点对称，跳过，继续检查下一对
if (t1 == null || t2 == null) return false;	一个 null 一个不是 → 结构不对称
if (t1.val != t2.val) return false;	两个都不是 null，但值不相等 → 数值不对称

入队顺序的核心逻辑

java

deque.offer(leftNode.left); // 第1个 deque.offer(rightNode.right); // 第2个 ← 和第1个是一对 deque.offer(leftNode.right); // 第3个 deque.offer(rightNode.left); // 第4个 ← 和第3个是一对

目的：让需要比较的两个节点在队列中紧挨着，这样取出来时自然成对。

图解：入队和取出的配对关系

text

当前正在比较：leftNode 和 rightNode 入队操作： ┌─────────────────────────────────────────┐ │ leftNode.left ─────┐ │ │ │ 成为一对 │ │ rightNode.right ────┘ │ │ │ │ leftNode.right ─────┐ │ │ │ 成为一对 │ │ rightNode.left ─────┘ │ └─────────────────────────────────────────┘ 队列内容：[L.left, R.right, L.right, R.left] ↑ ↑ ↑ ↑ └───┬───┘ └───┬───┘ 第1对 第2对

继续循环判断。

题目答案：

递归法：

/** * 递归法 */ public boolean isSymmetric1(TreeNode root) { return compare(root.left, root.right); } private boolean compare(TreeNode left, TreeNode right) { if (left == null && right != null) { return false; } if (left != null && right == null) { return false; } if (left == null && right == null) { return true; } if (left.val != right.val) { return false; } // 比较外侧 boolean compareOutside = compare(left.left, right.right); // 比较内侧 boolean compareInside = compare(left.right, right.left); return compareOutside && compareInside; }

迭代法：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isSymmetric(TreeNode root) { Queue<TreeNode> que=new LinkedList<>(); que.offer(root.left); que.offer(root.right); while(!que.isEmpty()){ TreeNode t1= que.poll(); TreeNode t2=que.poll(); if(t1==null&&t2==null){ continue; } if(t1==null||t2==null||t1.val!=t2.val){ return false; } que.offer(t1.left); que.offer(t2.right); que.offer(t1.right); que.offer(t2.left); } return true; }}

结语：如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！