Java实现LeetCode27：二叉树镜像详解

解题思路

LeetCode 第 27 题要求编写一个函数，输入一棵二叉树，输出它的镜像。所谓镜像，即把树中所有节点的左、右子节点互换位置。解决此问题的核心在于遍历整棵树并对每个节点执行交换操作。

方法一：递归法（DFS）

这是最直观且简洁的方法。根据镜像定义，只需从根节点开始，递归地交换当前节点的左右子节点即可。

算法步骤：

1. 终止条件：当访问到的节点为空（即越过叶子节点）时，直接返回 null。
2. 暂存节点：在交换前，先保存当前节点的左子节点引用到一个临时变量中。这是因为交换会改变节点的左子树指向，后续处理原左子树时需要该引用。
3. 递归右子树：对当前节点的右子节点调用镜像函数，并将返回值赋给当前节点的左指针。这一步不仅完成了交换，还生成了新的左子树。
4. 递归原左子树：对之前暂存的左子节点调用镜像函数，并将返回值赋给当前节点的右指针。
5. 返回结果：返回当前节点 root，表示该子树已处理完毕。

为什么需要暂存左子节点？
如果在第一步就执行 root.left = mirrorTree(root.right)，那么 root.left 的地址已经被右子树占据。此时再想对原来的左子树进行镜像处理时，已经找不到原左子树的入口了，从而导致逻辑错误或数据丢失。

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        // 1. 边界条件：空节点直接返回
        if (root == null) return null;
        
        // 2. 暂存原始的左子节点
        TreeNode tmp = root.left;
        
        // 3. 递归处理右子树，并赋值给左指针（完成镜像的第一步交换）
        root.left = mirrorTree(root.right);
        
        // 4. 递归处理暂存的原始左子树，并赋值给右指针（完成镜像的第二步交换）
        root.right = mirrorTree(tmp);
        
        // 5. 返回当前已反转的子树根节点
        return root;
    }
}

方法二：辅助栈（或队列）迭代法

如果不希望使用递归（例如考虑到递归深度过大导致栈溢出），可以使用迭代法。借助栈（或队列）来实现深度优先（或广度优先）遍历，逐层交换节点。

算法流程：

1. 特判：若根节点 root 为空，直接返回 null。
2. 初始化：创建一个栈 Stack，并将根节点 root 压入栈中。
3. 循环遍历：只要栈不为空，就持续弹出栈顶元素进行处理。
   • 出栈：取出当前处理的节点 node。
   • 添加子节点：如果 node 有左子节点或右子节点，分别将其压入栈中（等待后续处理其子节点的镜像）。
   • 交换：交换当前节点 node 的左右子节点引用。
4. 返回结果：整个栈空了，说明所有节点都已访问并交换完毕，返回根节点 root。

import java.util.Stack;

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        // 1. 边界处理
        if (root == null) return null;
        
        // 2. 初始化栈并加入根节点
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        // 3. 循环直到栈空
        while (!stack.isEmpty()) {
            // 弹出当前节点
            TreeNode node = stack.pop();
            
            // 记录左右子节点并压栈
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
            
            // 4. 交换左右子节点
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        
        // 5. 返回反转后的根节点
        return root;
    }
}

以上就是Java实现LeetCode27二叉树镜像的详细方法与代码解析，更多关于LeetCode经典题目与数据结构应用的资料请关注本站其它相关文章！