LeetCode 101 - 对称二叉树（Symmetric Tree）

问题描述

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

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

解题思路

对于二叉树的对称性问题，本质上是判断二叉树的左子树和右子树是否互为镜像。两个树互为镜像当且仅当：

它们的根节点的值相等
每个树的左子树和另一个树的右子树互为镜像
每个树的右子树和另一个树的左子树互为镜像

这个问题可以通过两种方式解决：递归和迭代。

方法一：递归

递归方法的核心思想是以递归的方式检查树的对称性。我们定义一个辅助函数，同时遍历左子树和右子树，进行必要的对称比较。

递归步骤：

如果左节点和右节点都为空，返回 true
如果只有一个节点为空，返回 false
如果两个节点的值不相等，返回 false
递归检查：
- 左节点的左子树与右节点的右子树是否对称
- 左节点的右子树与右节点的左子树是否对称

方法二：迭代（使用队列）

迭代方法使用队列来模拟递归过程。我们将需要比较的节点对依次放入队列，然后逐对取出进行比较。

迭代步骤：

初始化队列，放入根节点的左子节点和右子节点
当队列不为空时：
- 取出两个节点
- 如果都为空，继续下一轮循环
- 如果只有一个为空或值不相等，返回 false
- 将左节点的左子节点和右节点的右子节点放入队列
- 将左节点的右子节点和右节点的左子节点放入队列
队列为空时，返回 true

实现细节

递归实现

在递归实现中，我们定义了一个辅助函数 dfsIsSymmetric，用于检查两个节点是否对称：

func isSymmetric(root *TreeNode) bool {
    // 特殊情况处理：如果根节点为空，则树是对称的
    if root == nil {
        return true
    }
    // 调用辅助函数检查左右子树是否对称
    return dfsIsSymmetric(root.Left, root.Right)
}

func dfsIsSymmetric(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 dfsIsSymmetric(left.Left, right.Right) && dfsIsSymmetric(left.Right, right.Left)
}

迭代实现

以下是使用队列的迭代实现：

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
  
    // 使用队列进行BFS
    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)
        queue = append(queue, left.Right, right.Left)
    }
  
    return true
}

方法比较

方面	递归方法	迭代方法
时间复杂度	O(n)	O(n)
空间复杂度	O(h)，h是树的高度	O(n)
优点	代码简洁，易于理解	避免递归栈溢出风险
缺点	可能导致栈溢出	代码相对复杂
推荐度	★★★★★	★★★★☆

复杂度分析

时间复杂度：两种方法都是 O(n)，其中 n 是树中节点的数量。我们需要遍历树中的每个节点，对每个节点执行常数级操作。

空间复杂度：

递归方法：O(h)，其中 h 是树的高度。在最坏情况下（树是一条链），空间复杂度为 O(n)。
迭代方法：O(n)，队列中最多包含树中的所有节点。

关键收获

二叉树的镜像特性：理解如何判断两个树是否互为镜像是解决此类问题的关键。
递归与迭代的转换：这道题展示了如何将递归算法转换为迭代算法，这是一种重要的技术。
深度优先搜索（DFS）与广度优先搜索（BFS）：递归实现使用DFS，而队列实现使用BFS。

对于初学者，建议先理解递归解法，因为它更直观。掌握后，再尝试理解如何使用队列的迭代方法实现相同的功能。这种转换思路在许多树和图的问题中都非常有用。