71.对称二叉树

题目

给你一个二叉树的根节点 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

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

思路

递归

1. 终止条件

   • 两个都为空,是镜像，返回true
   • 只有一个为空，结构不对称，返回false
   • 两个都非空，比较值，进入下一步

2. 递推关系(两个都非空时)

   • 先看当前两个节点的值: 如果 a.val != b.val，不镜像，false
   • 如果a.val == b.val, 那值相等，就交叉递归
     • a的左孩子 vs b的右孩子: isMirror(a.left, b.right)
     • a的右孩子 vs b的左孩子: isMirror(a.right, b.left)
     • 上面这两个都为true才算镜像

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun isSymmetric(root: TreeNode?): Boolean {
        // 空树认为是对称的
        if (root == null) {
            return true
        }
        // 对称 ⟺ 左子树和右子树互为镜像
        return isMirror(root.left, root.right)
    }

    /**
     * 判断以 a、b 为根的两棵树是否互为镜像
     */
    private fun isMirror(a: TreeNode?, b: TreeNode?): Boolean {
        // 1. base case 之一：两个都为空 → 镜像
        if (a == null && b == null) {
            return true
        }

        // 2. base case 之二：只有一个为空 → 不对称
        if (a == null || b == null) {
            return false
        }

        // 3. 两个都非空：先比较值
        if (a.`val` != b.`val`) {
            return false
        }

        // 4. 交叉递归：a的左 ↔ b的右（外侧），a的右 ↔ b的左（内侧）
        return isMirror(a.left, b.right) && isMirror(a.right, b.left)
    }
}

BFS(迭代，用队列成对比较)

也可以不用递归，用队列。

技巧是: 每次从队列成对地取出两个节点来比较，入队时也成对入队，并且入队顺序要体现交叉。

import java.util.LinkedList

class Solution {
    fun isSymmetric(root: TreeNode?): Boolean {
        if (root == null) return true

        val queue: java.util.Queue<TreeNode?> = LinkedList()
        // 初始把左右子树成对入队
        queue.offer(root.left)
        queue.offer(root.right)

        while (queue.isNotEmpty()) {
            // 每次取出一对来比较
            val a = queue.poll()
            val b = queue.poll()

            // 都空，这一对匹配，跳过继续
            if (a == null && b == null) continue
            // 一空一非空，或值不等 → 不对称
            if (a == null || b == null || a.`val` != b.`val`) return false

            // 成对入队，注意交叉顺序：
            queue.offer(a.left)   // 外侧一对：a.left 与 b.right
            queue.offer(b.right)
            queue.offer(a.right)  // 内侧一对：a.right 与 b.left
            queue.offer(b.left)
        }

        return true
    }
}

复杂度

• 时间复杂度: O(n)：每个节点最多被访问一次（一旦发现不对称就短路返回）。
• 空间复杂度: O(h)：h 是树高，来自递归调用栈。最坏（退化成链）O(n)，平衡树 O(log n)。

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!