快手一面：给定一棵二叉树，要求将其转换为其镜像？

题解：二叉树的镜像（Invert Binary Tree）

问题描述

给定一棵二叉树，要求将其转换为其镜像。也就是说，交换每个节点的左子树和右子树。

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例

输入：

     4/   \2     7/ \   / \
1   3 6   9

输出：

     4/   \7     2/ \   / \
9   6 3   1

解题思路

要将一棵二叉树转换为其镜像，可以通过递归的方法来实现。具体步骤如下：

1. 基本情况：如果当前节点为空，则直接返回 null。
2. 交换左右子树：对于当前节点，交换其左子树和右子树。
3. 递归处理子树：对新的左子树和右子树分别进行递归调用，继续交换它们的左右子树。
4. 返回根节点：最终返回根节点，此时整棵树已经被转换为其镜像。

代码实现

class Solution {// 递归 子问题 树的左右子树反转 并返回根节点public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}// 交换当前节点的左右子树TreeNode tmp = root.right;root.right = root.left;root.left = tmp;// 递归处理左子树invertTree(root.left);// 递归处理右子树invertTree(root.right);// 返回根节点return root;}
}

详细分析

1. 基本情况处理：

   • 如果根节点 root 为空，说明当前子树为空，直接返回 null。

2. 交换左右子树：

   • 使用一个临时变量 tmp 来保存当前节点的右子树。
   • 将当前节点的右子树设置为当前节点的左子树。
   • 将当前节点的左子树设置为临时变量 tmp 中保存的右子树。

3. 递归处理子树：

   • 对新的左子树调用 invertTree 方法，继续交换其左右子树。
   • 对新的右子树调用 invertTree 方法，继续交换其左右子树。

4. 返回根节点：

   • 最终返回根节点 root，此时整棵树已经被转换为其镜像。

复杂度分析

• 时间复杂度：

  • 每个节点都需要被访问一次，并且每次访问时需要进行常数时间的操作（交换左右子树）。
  • 因此，总的时间复杂度为 O(n)，其中 n 是树中节点的数量。

• 空间复杂度：

  • 递归调用栈的空间复杂度取决于树的高度。
  • 在最坏情况下（树完全不平衡，退化成链表），空间复杂度为 O(n)。
  • 在最好情况下（树完全平衡），空间复杂度为 O(log n)。

优点

• 简洁性：代码非常简洁，易于理解和实现。
• 高效性：通过递归方法，可以有效地遍历并交换每个节点的左右子树。

注意事项💕

• 空树处理：在开始递归之前，先检查根节点是否为空，以避免不必要的操作。
• 递归终止条件：确保在递归过程中正确处理空子树的情况，防止出现空指针异常。
• 交换当前节点的左右子树的代码位置是关键的
  • 为什么这段代码要写在这个位置？
  • 交换操作在递归调用之前，确保每次递归调用时，当前节点的左右子树已经被正确交换。这里是用到了前序遍历，从上到下，从根节点向下操作，所以用前序遍历！！