LeetCode 剑指 Offer 27. 二叉树的镜像

Categories:

Tags:

题目描述
思路分析
1. 解法一：递归后序遍历（推荐）
2. 解法二：BFS 层序遍历
相似题目

题目描述

✅ 剑指 Offer 27. 二叉树的镜像

思路分析

解法一：递归后序遍历（推荐）

核心思路：

翻转二叉树等价于：对每个节点，交换其左右子节点，并对左右子树递归执行同样操作。

采用后序遍历：先递归翻转左子树，再递归翻转右子树，最后交换当前节点的左右子节点。

递归终止条件：当前节点为空时直接返回。

复杂度分析：

时间复杂度：O(n)，其中 n 表示二叉树的节点总数，每个节点恰好被访问一次。

空间复杂度：O(n)，其中 n 表示二叉树的节点总数，递归调用栈的深度最坏情况下（链状树）为 O(n)。

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        // 递归终止：空节点直接返回
        if (root == null) {
            return null;
        }
        // 先递归翻转左子树
        TreeNode left = mirrorTree(root.left);
        // 再递归翻转右子树
        TreeNode right = mirrorTree(root.right);
        // 交换当前节点的左右子节点
        root.left = right;
        root.right = left;
        return root;
    }
}

func mirrorTree(root *TreeNode) *TreeNode {
    // 递归终止：空节点直接返回
    if root == nil {
        return nil
    }
    // 先递归翻转左子树
    left := mirrorTree(root.Left)
    // 再递归翻转右子树
    right := mirrorTree(root.Right)
    // 交换当前节点的左右子节点
    root.Left = right
    root.Right = left
    return root
}

解法二：BFS 层序遍历

核心思路：

使用队列进行层序遍历，逐层处理每个节点。

对于出队的每个节点，直接交换其左右子节点，然后将非空的子节点加入队列继续处理。

遍历结束后，整棵树已完成镜像翻转。

复杂度分析：

时间复杂度：O(n)，其中 n 表示二叉树的节点总数，每个节点恰好被访问一次。

空间复杂度：O(n)，其中 n 表示二叉树的节点总数，队列中最多同时存储一层的节点，最坏情况下为 O(n)。

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        // 使用队列进行层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 交换当前节点的左右子节点
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            // 将非空子节点加入队列
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return root;
    }
}

func mirrorTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    // 使用切片模拟队列进行层序遍历
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        // 交换当前节点的左右子节点
        node.Left, node.Right = node.Right, node.Left
        // 将非空子节点加入队列
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }
    return root
}

相似题目

题目	难度	考察点
226. 翻转二叉树	简单	递归 / BFS / DFS
101. 对称二叉树	简单	递归 / 镜像判断
100. 相同的树	简单	递归 / 树结构比较
572. 另一棵树的子树	简单	递归 / 子树匹配
951. 翻转等价二叉树	中等	递归 / 翻转等价
104. 二叉树的最大深度	简单	递归 / DFS / BFS
112. 路径总和	简单	递归 / DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/98031428