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

目录标题

- - 题解：二叉树的镜像（Invert Binary Tree）
  - - 问题描述
    - 示例
    - 解题思路
    - 代码实现
    - 详细分析
    - 复杂度分析
    - 优点
    - 注意事项💕

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

问题描述

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

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

示例

输入：

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

输出：

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

在这里插入图片描述

解题思路

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

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

代码实现

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

详细分析

基本情况处理：
- 如果根节点 root 为空，说明当前子树为空，直接返回 null。
交换左右子树：
- 使用一个临时变量 tmp 来保存当前节点的右子树。
- 将当前节点的右子树设置为当前节点的左子树。
- 将当前节点的左子树设置为临时变量 tmp 中保存的右子树。
递归处理子树：
- 对新的左子树调用 invertTree 方法，继续交换其左右子树。
- 对新的右子树调用 invertTree 方法，继续交换其左右子树。
返回根节点：
- 最终返回根节点 root，此时整棵树已经被转换为其镜像。

复杂度分析

时间复杂度：
- 每个节点都需要被访问一次，并且每次访问时需要进行常数时间的操作（交换左右子树）。
- 因此，总的时间复杂度为 O(n)，其中 n 是树中节点的数量。
空间复杂度：
- 递归调用栈的空间复杂度取决于树的高度。
- 在最坏情况下（树完全不平衡，退化成链表），空间复杂度为 O(n)。
- 在最好情况下（树完全平衡），空间复杂度为 O(log n)。

优点

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

注意事项💕

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

在这里插入图片描述