力扣 – 剑指 Offer 27. 二叉树的镜像

• 2021 年 11 月 24 日
• 笔记
• BFS, DFS, 二叉树, 算法与题解, 迭代, 递归

题目

剑指 Offer 27. 二叉树的镜像

思路1（递归）

• 我们可以使用深度优先搜索，先递归到链表的末尾，然后从末尾开始两两交换。就相当于后续遍历而已
• 记得要先保存下来node.right节点，因为我们在递归完左边才递归右边，而递归完左边的时候，直接把node.right的指向修改了，如果事先不保存node.right节点的话，在递归右边传入的节点是错误的节点，因此得不到正确的答案

代码

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        return dfs(root);
    }

    public TreeNode dfs(TreeNode node) {
        // 为空说明到底了
        if (node == null) {
            return null;
        }

        // 先记录right节点
        TreeNode right = node.right;

        // 分别递归左边和右边，将 left 和 right 的指针互相交换
        node.right = mirrorTree(node.left);
        node.left = mirrorTree(right);

        return node;
    }
}

复杂度分析

• 时间复杂度：\(O(N)\)，遍历一遍树的每个节点要花费\(O(N)\)的时间复杂度
• 空间复杂度：\(O(N)\)，最坏情况下是一条链表，因此递归需要\(O(N)\)的栈空间

思路2（迭代）

• 使用队列（也可以使用栈，差不多一样）进行存储节点，就是数的层序遍历
• 节点是按顺序入队，因此我们需要做的就是将队头元素出队，然后将他的两个子节点入队，再交换两个子节点的值就可以完成一个子节点左右孩子的交换，重复所有的节点
• 其实就是从树根到树叶将每个子节点都进行交换，最终完成了整个树的交换，形成镜像

代码

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();
            // 将子节点入队
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            // 交换左右两个子节点
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
        }

        return root;
    }
}

复杂度分析

• 时间复杂度：\(O(N)\)
• 空间复杂度：\(O(N)\)，栈最多存储 \(\frac{N + 1}{2}\)个节点