面试经典150题——对称二叉树

1. 题目描述

2. 题目分析与解析

2.1 思路一——递归

为了解决问题“检查一个二叉树是否是对称的”，我们需要判断树的左子树和右子树是否是彼此的镜像。这意味着树的左子树的左侧应该与右子树的右侧相同，左子树的右侧应该与右子树的左侧相同。

1. 定义问题：
   对称二叉树的定义是，一个树和它的镜像是相同的。即根节点的左子树和右子树镜像对称。
2. 基本情况：
   • 如果两个树的根节点都为空，则它们是对称的。
   • 如果一个树的根节点为空而另一个不为空，则它们不对称。
3. 递归逻辑：
   • 对于两个节点，检查它们的值是否相等。
   • 如果相等，进一步检查第一个树的左子树与第二个树的右子树是否对称，以及第一个树的右子树与第二个树的左子树是否对称。
4. 递归实现：
   • 我们可以定义一个辅助函数 check(TreeNode p, TreeNode q)，它接受两个节点，并返回一个布尔值表示这两个子树是否对称。
   • 我们首先检查 p 和 q 是否都不为空。
   • 然后比较 p 和 q 的值，如果它们相等，再递归地调用 check(p.left, q.right) 和 check(p.right, q.left)。
5. 整体函数：
   • 主函数 isSymmetric(TreeNode root) 判断整个树是否对称，只需调用 check(root, root)。

实际上就是判断一个树是否沿中轴对称就是看它看作两个树：

• 如果两个根节点的值不相等，那么返回false，确保根节点的值相等
• 如果根节点的左值与另一个根节点的右值不等，或者根节点的右值与另一个根节点的左值不等，那么返回false
• 只有当根节点的值相等，且根节点的左右子节点分别与另一个根节点的右左子节点相等时，才返回true

2.2 思路二——迭代

因为在理论上，任何递归算法都可以被转换为迭代算法。这是因为递归本质上是函数自调用，使用的是计算机的调用栈来保存状态；而迭代算法使用的是循环结构，在循环中显式使用数据结构（如栈或队列）来保存状态和管理控制流。

因此我们将递归算法改为迭代来解决。这种方法是将递归的深度优先搜索（DFS）转换为广度优先搜索（BFS），利用队列实现。下面是这种方法的详细解释和思路：

初始化

首先，定义一个队列 q，类型为 Queue<TreeNode>，用来存放需要比较的节点对。初始时，将根节点 root 两次加入队列，代表要比较树的左半边与右半边。

迭代过程

1. 循环遍历：
   使用一个 while 循环来处理队列中的元素，直到队列为空。在每次循环中，从队列中取出两个节点（u 和 v），这两个节点是需要比较的对称节点。

2. 节点比较：

   • 如果两个节点都为 null，则继续下一轮循环（这表示对称位置的两个分支都正确地结束了）。
   • 如果一个节点为 null 而另一个不为 null，或者两个节点的值不相等，则树不对称，函数返回 false。

3. 节点的子节点入队：

   • 将 u 的左子节点和 v 的右子节点入队，这两个节点在对称的二叉树中应该是相等的。
   • 将 u 的右子节点和 v 的左子节点入队，同样，这两个节点在对称的二叉树中应该是相等的。

结束条件

• 如果队列被完全处理完并且在所有比较中节点都匹配（即没有提前返回 false），则函数返回 true，表明这棵树是对称的。

2.3 思路三

这种解题思路通过直接修改树的结构来判断二叉树是否对称，具体通过翻转二叉树的左子树，然后判断翻转后的左子树与原始的右子树是否完全相同。这里的核心思想是，如果一棵树的左子树是右子树的镜像，那么将左子树翻转后，它应该与右子树完全相同。

翻转左子树 (reverse 方法)

1. 递归翻转：

   • 如果当前节点为 null，返回 null，表示该分支已处理完。
   • 递归翻转当前节点的左子节点，并存储返回的新根节点。
   • 递归翻转当前节点的右子节点。
   • 将当前节点的左指针指向翻转后的右子树，右指针指向翻转后的左子树。

2. 返回翻转后的根节点：

   • 每次递归调用后，返回当前节点，它现在代表翻转后的子树。

判断两棵树是否相同 (isSameTree 方法)

1. 递归比较两个树：
   • 如果两个节点都为 null，返回 true，表示对应的子树在这一层都结束，且相同。
   • 如果其中一个节点为 null 而另一个不为 null，返回 false，表示树结构不同。
   • 比较两个节点的值是否相等，如果不相等，返回 false。
   • 递归比较左子节点和左子节点，右子节点和右子节点。

主函数逻辑

• 翻转左子树：

  • 调用 reverse 方法对 root.left 进行翻转。

• 比较翻转后的左子树和原右子树：

  • 调用 isSameTree 方法比较 root.left（翻转后的左子树）和 root.right（原始的右子树）。

3. 代码实现

3.1 思路一

3.2 思路二

3.3 思路三

4. 相关复杂度分析

方法1: 使用递归

时间复杂度

• 这种方法通过递归访问每一个节点，对于每个节点，递归比较其左子节点和对称的右子节点。
• 最坏情况下，每个节点都会被访问一次，因此时间复杂度为 $O(n)$，其中 $n$ 是树中节点的数量。

空间复杂度

• 由于使用递归，主要的空间消耗来自于递归栈。
• 在最坏的情况下（当树完全不平衡时），递归的深度可以达到 $n$，因此空间复杂度为 $O(n)$。
• 在最佳情况下（树完全平衡时），递归深度为 $O(\log n)$，因此空间复杂度为 $O(\log n)$。

方法2: 使用迭代

时间复杂度

• 使用一个队列来按层比较节点，确保每个节点都被访问并比较一次，所以时间复杂度为 $O(n)$。

空间复杂度

• 在最坏的情况下，队列中可能包含接近 $n/2$ 个节点（考虑到最后一层的宽度），因此空间复杂度也为 $O(n)$。

方法3: 翻转左子树后比较两子树

时间复杂度

• reverse 函数遍历所有节点一次，时间复杂度为 $O(n/2)=O(n)$，因为只翻转左子树。
• isSameTree 函数也遍历所有节点一次，时间复杂度为 $O(n)$。
• 总的时间复杂度为 $O(n)$。

空间复杂度

• reverse 和 isSameTree 函数都使用递归，因此空间复杂度主要由递归栈决定。
• 在最坏情况下，递归深度可以达到 $n$（非平衡树），因此空间复杂度为 $O(n)$。
• 在最佳情况下（树完全平衡时），递归深度为 $O(\log n)$，因此空间复杂度为 $O(\log n)$。