对称二叉树的判定：双端队列的精妙应用-CSDN博客

本文链接：https://blog.csdn.net/Musennn/article/details/148014457

一、题目解析

题目描述

给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的：

而 [1,2,2,null,3,null,3] 则不是镜像对称的：

问题本质

判断一棵二叉树是否镜像对称，等价于判断其左子树和右子树是否互为镜像。具体来说，需要满足以下条件：

根节点的值相同
每个树的左子树与另一个树的右子树镜像对称

二、双端队列解法思路

核心思想

使用双端队列（Deque）同时存储待比较的节点对，通过队列两端的操作，确保每次取出的节点对是需要比较的镜像节点。具体步骤如下：

将根节点的左右子节点分别从队列的前端和后端入队
每次循环从队列两端各取出一个节点进行比较
若两节点均为空，继续循环
若两节点中只有一个为空或值不相等，返回 false
若两节点均非空且值相等，将它们的子节点按镜像关系入队：
- 左子树的左节点与右子树的右节点入队
- 左子树的右节点与右子树的左节点入队

代码实现

/**
 * 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) {
        Deque<TreeNode> cur = new LinkedList<>();
        if (root == null) {
            return true;
        }
        TreeNode tempLeft = root.left;
        TreeNode tempRight = root.right;
        cur.offerFirst(tempLeft);
        cur.offerLast(tempRight);
        while (!cur.isEmpty()) {
            tempLeft = cur.pollFirst();
            tempRight = cur.pollLast();
            if (tempLeft == null && tempRight == null) {
                continue;
            }
            if (tempLeft == null || tempRight == null || tempLeft.val != tempRight.val) {
                return false;
            }
            cur.offerFirst(tempLeft.left);
            cur.offerFirst(tempLeft.right);
            cur.offerLast(tempRight.right);
            cur.offerLast(tempRight.left);
        }
        return true;
    }
}

三、代码详细解释

初始化与边界处理

Deque<TreeNode> cur = new LinkedList<>();
if (root == null) {
    return true;
}
TreeNode tempLeft = root.left;
TreeNode tempRight = root.right;
cur.offerFirst(tempLeft);
cur.offerLast(tempRight);

创建双端队列 cur 用于存储待比较的节点对
若根节点为空，直接返回 true（空树视为对称）
将根节点的左右子节点分别从队列的前端和后端入队

主循环处理

while (!cur.isEmpty()) {
    tempLeft = cur.pollFirst();
    tempRight = cur.pollLast();
    if (tempLeft == null && tempRight == null) {
        continue;
    }
    if (tempLeft == null || tempRight == null || tempLeft.val != tempRight.val) {
        return false;
    }
    // 处理子节点
}

每次循环从队列前端和后端各取出一个节点
若两节点均为空，跳过当前循环
若两节点中只有一个为空或值不相等，说明不对称，返回 false

子节点处理

cur.offerFirst(tempLeft.left);
cur.offerFirst(tempLeft.right);
cur.offerLast(tempRight.right);
cur.offerLast(tempRight.left);

将左子树的左节点和右节点依次从队列前端入队
将右子树的右节点和左节点依次从队列后端入队
这样确保了下一次循环时，左子树的左节点会与右子树的右节点比较，左子树的右节点会与右子树的左节点比较

四、算法示例演示

以对称二叉树 [1,2,2,3,4,4,3] 为例，展示队列的变化过程：

初始状态

队列: [2, 2]

第一次循环

取出 2 和 2
值相等，处理子节点：
- 左子树的左节点 3 入队首
- 左子树的右节点 4 入队首
- 右子树的右节点 3 入队尾
- 右子树的左节点 4 入队尾

队列: [3, 4, 4, 3]

第二次循环

取出 3 和 3
值相等，无子节点，队列变为 [4, 4]

第三次循环

取出 4 和 4
值相等，无子节点，队列为空
返回 true

五、复杂度分析

时间复杂度：O(n)，每个节点仅被访问一次
空间复杂度：O(h)，h为树的高度，最坏情况下为O(n)

六、双端队列的优势

使用双端队列的关键在于能够同时维护两个方向的节点对，通过以下操作实现镜像比较：

offerFirst() 和 pollFirst() 处理左子树节点
offerLast() 和 pollLast() 处理右子树节点
这种设计使得每次取出的节点对恰好是需要比较的镜像节点，避免了递归或单队列方法中的额外处理逻辑

七、总结

双端队列解法通过巧妙的入队和出队策略，将镜像比较的逻辑转化为队列两端的操作，既保持了迭代方法的优势（避免栈溢出），又直观地实现了节点对的比较。理解这种解法的关键在于把握队列操作与镜像关系的对应：

左子树的左节点 → 队列前端
左子树的右节点 → 队列前端
右子树的右节点 → 队列后端
右子树的左节点 → 队列后端

这种对称性的设计使得代码简洁高效，是解决对称二叉树问题的一种优雅方式。