忍者算法

Appearance

对称二叉树：镜子中完美的平衡 ​

对称的诗意：生活中的平衡美学 ​

想象一个完美的世界，两侧如同镜像般精准对称。在自然界中，对称常常意味着美感和和谐。二叉树的对称性也是如此 —— 一种近乎艺术的数学之美，它不仅仅是结构，更是一种深层的平衡哲学。

对称的本质：镜面的数学逻辑 ​

对称二叉树（LeetCode第101题）是一种特殊的树，它要求：

  1. 根节点的左右子树完全镜像
  2. 对应位置的节点具有相同的值
  3. 树的结构在轴心处完美对折

这就像是一个精心设计的万花筒，每一个角度都呈现出令人惊叹的平衡。

递归解法：镜像对比的优雅 ​

java
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;
    
    // 判断三个条件：
    // 1. 当前节点值相同
    // 2. 左子树的左边 = 右子树的右边
    // 3. 左子树的右边 = 右子树的左边
    return (left.val == right.val) && 
           isMirror(left.left, right.right) && 
           isMirror(left.right, right.left);
}

代码的深层逻辑解析 ​

  1. 第一层方法 isSymmetric()

    • 处理根节点特殊情况
    • 将复杂的对称判断委托给专门的镜像比较方法

  2. 镜像比较方法 isMirror()

    • 首先处理节点为空的边界情况
    • 要求左右子树节点值相同
    • 递归比较左右子树的镜像位置

迭代方法：显式的对称之旅 ​

java
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;
}

迭代方法的独特视角 ​

  • 显式地模拟镜像遍历
  • 使用队列管理节点配对
  • 每次处理两个对应位置的节点
  • 避免了递归可能的栈空间问题

性能分析：效率的数学之美 ​

时间复杂度：O(n) ​

  • 每个节点仅访问一次
  • n为树中节点总数
  • 无论递归还是迭代，都高效地遍历整棵树

空间复杂度 ​

  • 递归版本：O(h)，h为树的高度
    • 最坏情况可达O(n)
    • 最好情况（平衡树）为O(log n)
  • 迭代版本：O(w)，w为树的最大宽度
    • 通常空间效率更可控

递归的诗：平衡与重复的艺术 ​

对称二叉树不仅仅是一道算法题，更是递归思想的诗意表达。它启示我们：

  • 复杂的对称可以通过简单的重复规则构建
  • 递归是理解对称性的强大工具
  • 代码的优雅源于思维的对称与平衡

探索对称二叉树就像在知识的镜子中发现宇宙的韵律，重要的是保持好奇和对美的敏感！

作者：忍者算法 公众号：忍者算法

🎯 回复【刷题清单】获取更多经典题目解析 👥 回复【加群】加入算法/面试交流群，一起学习进步 🧑‍💻 回复【代码】获取GitHub完整题解项目，包含Java/Python/JavaScript/Go/C++多语言实现

#算法面试 #LeetCode #数据结构