Mirror Tree in Java

Java 中的镜像树是指通过交换每个子树的左右子节点来创建二叉树的镜像版本。此过程会生成原始树结构的对称反射。通常使用递归或迭代方法来解决。

输入 1 2 3 4 5

输出 1 3 2 5 4

解释

输出表示了原始二叉树的镜像版本。在交换了每个节点的左右子节点后，树结构被翻转。在此示例中，节点 2 的左右子节点（4 和 5）被交换，同样，节点 1 的左右子节点（2 和 3）也被交换。

方法 1：使用递归方法

算法

步骤 1：从根节点开始：从树的根节点开始，它是镜像操作的入口点。在此节点，第一步是交换其左右子节点。此操作启动了镜像过程，确保在递归进行时，整个树都会被反射。

步骤 1.1：验证根节点：检查树的根节点是否为 null。如果根节点为 null，则树为空，无需进一步处理。立即返回，因为没有节点需要镜像。

步骤 2：交换子节点：在每个节点，执行以下操作：

临时保存节点的左子节点。

将右子节点赋值给左子节点。

将保存的左子节点赋值给右子节点。

简单来说，我们在每个节点上交换左右子树。

步骤 3：递归处理树：交换当前节点的子节点后

移动到左子节点并执行相同的步骤（交换子节点，然后重复）。

移动到右子节点并重复步骤。递归确保树中的所有节点都被处理。

步骤 3.1：递归处理左子树：在当前节点交换左右子节点后，移动到左子节点（现在是原始的右子节点）。对该左子节点递归调用镜像函数。这确保了整个左子树都被处理，并且其子节点以相同的方式被镜像。

步骤 4：在空节点处停止：当递归到达空节点（不存在的节点）时，停止处理。空节点没有子节点，因此无需进一步操作。

步骤 4.1：处理空节点：当递归到达空节点（没有值或缺少子节点的节点）时，停止进一步处理。没有子节点可以交换或镜像，因此只需返回并回溯到前一个节点。这可以防止对不存在节点的不必要操作。

步骤 5：返回更新后的树：在所有节点的子节点都交换并且递归完成之后，树就成为了自身的镜像。

将镜像树的根节点作为最终结果返回。

步骤 5.1：返回镜像树：在所有节点都交换了它们的左右子节点并且递归完成之后，树就完全被镜像了。最后一步是返回树的根节点，它现在代表了原始树的镜像版本，所有子树都被对称地反射了。

文件名：MirrorTree.java

输出

 
Original Tree (In-order):
4 2 5 1 3 
Mirrored Tree (In-order):
3 1 5 2 4   

复杂度分析

时间复杂度

镜像二叉树的时间复杂度为 O(n)，其中 n 是树中的节点数。这是因为树中的每个节点都会被访问一次以交换其子节点，并且递归确保所有节点都以线性时间被处理。

空间复杂度

镜像二叉树的空间复杂度为 O(h)，其中 h 是树的高度。这是由于递归函数调用使用了系统的调用堆栈。在最坏的情况下，对于一个倾斜的树，空间复杂度为 O(n)，其中 n 是节点数。

方法 2：使用迭代方法

算法

步骤 1：检查树是否为空：首先要做的就是检查树是否存在。如果树为空（根节点为 null），则无需镜像。在这种情况下，函数将立即返回，因为无需进一步处理。这处理了输入无效或树不包含任何节点的情况。

步骤 2：设置队列：由于我们不使用递归，我们需要一种不同的方法来遍历树的所有节点。队列是理想的选择，因为它允许我们按先进先出 (FIFO) 的顺序处理节点。我们将从将根节点放入队列开始。这确保我们按层级处理树，从根开始向下移动。

步骤 3：逐个处理节点：现在我们将通过从队列中移除节点来逐个处理树中的节点。对于每个节点，我们执行以下步骤：

交换子节点：二叉树中的每个节点都有两个可能的子节点：左子节点和右子节点。要镜像树，我们需要交换当前节点的左子节点和右子节点。

例如，如果一个节点的左子节点是 2，右子节点是 3，交换后，左子节点将是 3，右子节点将是 2。

将子节点添加到队列：交换子节点后，我们将它们添加到队列（但前提是它们存在）。例如，如果当前节点有左子节点或右子节点，我们将它们入队，以便稍后处理。这确保树中的每个节点最终都被访问和镜像。

步骤 4：重复直到所有节点都被处理：我们继续这个过程：从队列中移除节点，交换它们的子节点，并将子节点重新添加到队列中，直到队列变空。队列变空意味着我们已经处理了树中的所有节点，并且镜像过程已经完成。

步骤 4.1：验证树结构

在处理完所有节点并交换它们的子节点后，您可以遍历树（例如，使用中序或层序遍历）来确认结构是否已正确镜像。此步骤有助于验证算法的正确性，尤其是在测试或调试期间。验证后，继续返回镜像树的根。

步骤 5：返回根节点：一旦所有节点都被处理并且它们的子节点都已交换，树现在就已镜像。函数将返回树的根节点，它代表了输入树的完全镜像版本。

文件名：MirrorTreeIterative.java

输出

 
Original Tree (In-order):
4 2 5 1 3 
Mirrored Tree (In-order):
3 1 5 2 4   

复杂度分析

时间复杂度

镜像二叉树的迭代方法的时间复杂度为 O(n)，其中 n 是树中的节点数。每个节点都会被处理一次（访问、交换子节点并根据需要添加到队列），确保算法相对于树的大小以线性时间完成。

空间复杂度

镜像二叉树的迭代方法空间复杂度为 O(w)，其中 w 是树的最大宽度。这是因为队列一次会存储一棵树级别的节点。在最坏的情况下（满二叉树），w ≈ n/2。