Java实现二叉树镜像：递归与非递归方法

剑指offer题解（Java版）是一份专注于帮助求职者准备面试的资料，主要关注于IT技术面试中的问题解答。本部分讨论的是一个特定的题目——二叉树镜像。题目要求对给定的二叉树进行操作，使其转换成源二叉树的镜像，即左右子节点互换，保持原有的层次结构。 题目描述的场景是NowCoder编程面试练习题，给出了一个示例，源二叉树的结构如下： ``` 8 / \ 6 10 / \ / \ 5 7 9 11 ``` 目标是将其变换为镜像二叉树： ``` 8 / \ 10 6 / \ / \ 11 9 7 5 ``` 解题思路主要包括两种方法： **方法一：递归** 递归是一种自然的选择，因为二叉树的镜像本质上是对树的层次进行翻转。这里，作者提供了一个名为`Solution`的类，其中包含一个名为`mirror`的方法，用于处理这个问题。在方法内部，首先检查根节点是否为空，然后判断当前节点是否有子节点。如果有，将左子节点赋值给临时变量`pTemp`，然后将根节点的左子节点设置为右子节点，右子节点设置为`pTemp`。接着递归地对左子节点和右子节点进行同样的操作，直到所有非叶子节点都被处理完毕。 **方法二：非递归（利用栈）** 另一种解决方案是非递归的，通过使用一个`Stack`来模拟递归过程。首先，将根节点压入栈中。然后进入一个循环，只要栈不为空，就从栈中弹出一个节点，交换其左右子节点，然后将左子节点和右子节点（如果存在）分别压入栈中。这样，通过不断交替弹出和压入节点，可以确保所有的子节点都按照镜像顺序被处理。 总结来说，解决二叉树镜像问题的关键在于理解如何在递归或非递归环境下遍历二叉树，并根据题目要求对节点关系进行调整。这两种方法都可以有效地完成任务，但递归方法更直观，而非递归方法则展示了栈这种数据结构在算法中的实际应用。无论是面试中还是日常编程，理解这些基本的二叉树操作都是提高技术水平和解决问题能力的重要一步。