力扣 – 劍指 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}\)個節點