在 Java 中反转二叉树

在计算机科学和编程中，反转或镜像二叉树是一种常见的操作。它会颠倒每个节点左右子树的排列，有效地创建出原始树的镜像图像。

这个过程本质上是围绕垂直轴镜像树。在二叉树操作中，反转是一种常用的操作，它在优化与树相关的各种算法中起着关键作用。该概念涉及递归地遍历树并交换每个节点的左右子节点的位置。

方法：递归遍历树

递归遍历树是一种用于探索和处理树状结构（或框）中的节点的方法。该方法将遍历树的任务分解成更小、更易于管理的步骤。

算法

步骤 1： 创建一个 BinaryTreeNode 类来表示二叉树的节点。它有一个数字（值）、一个左子节点和一个右子节点。它还提供了一种在创建节点时初始化值的方式。

步骤 2： 创建一个名为 BinaryTreeMirrorConverter 的类，它将帮助我们将二叉树转换为其镜像。该类有一个名为 root 的变量，指向树的起始节点。

步骤 3： 在 BinaryTreeMirrorConverter 类中，创建一个名为 convertToMirror 的方法。它通过调用一个辅助方法并将根节点作为参数来改变树的根。

步骤 4： 创建一个名为 convertToMirror 的辅助方法。它接收树中的一个节点并执行以下操作：

• 如果该节点为空（null），则返回它。
• 如果节点不为空，则通过分别调用此方法来反转节点的左右子节点，然后交换它们。
• 最后，返回更新后的节点。

步骤 5： 在 BinaryTreeMirrorConverter 类中，创建一个名为 inorderTraversal 的方法。它有助于我们以特定的顺序遍历树。

步骤 6： 创建一个名为 inorderTraversal 的辅助方法。它接收树中的一个节点，如果该节点不为空，则先访问左子节点，然后打印节点的值，最后访问右子节点。

步骤 7： 在我们程序的 main 部分，创建一个名为 tree 的新 BinaryTreeMirrorConverter 对象。按照特定顺序构建一个包含一些数字的树。以某种顺序（中序遍历）显示树中的数字。将树反转为其镜像。然后以相同的顺序显示镜像树中的数字。

实施

文件名： BinaryTreeMirrorConverter.java

输出

Inorder traversal of the original tree:
4 2 5 1 3 
Inorder traversal of the mirrored tree:
3 1 5 2 4

时间复杂度： 时间复杂度为 O(n)，其中 n 是二叉树中的节点数。在镜像转换过程中，每个节点都会被访问一次。

辅助空间： 辅助空间复杂度为 O(h)，其中 h 是二叉树的高度。递归栈空间是辅助空间的一部分。

方法：层序遍历

层序遍历是一种树遍历算法，它从树的根节点开始，逐层从左到右访问节点。该方法使用队列来管理节点探索的顺序，最初将根节点入队。

算法

步骤 1： 定义一个 TreeNode 类，包含 int data、TreeNode left 和 TreeNode right 属性。

步骤 2： 定义一个 BinaryTree 类，其中包含静态方法。

步骤 3： 在 main 方法中，创建一个示例二叉树。

步骤 4： 打印原始二叉树的中序遍历。

步骤 5： 调用 convertToMirror 方法，并将二叉树的根节点作为参数传递。

步骤 6： 在 convertToMirror 方法中：

• 使用队列进行层序遍历。
• 交换每个节点的左右子节点。
• 如果左右子节点存在，则将它们入队。

步骤 7： 打印镜像二叉树的中序遍历。

实施

文件名： BinaryTree.java

输出

Original Binary Tree (Inorder Traversal):
4 2 5 1 3 
Mirrored Binary Tree (Inorder Traversal - Mirror Image):
3 1 5 2 4

时间复杂度： 时间复杂度为 O(n)，其中 n 是二叉树中的节点数。这是因为在层序遍历过程中，每个节点都会被访问一次。

辅助空间： 辅助空间复杂度为 O(w)，其中 w 是二叉树的最大宽度（任意层上的节点数）。