題?描述

操作給定的?叉樹，將其變換為源?叉樹的鏡像。

?叉樹的鏡像定義：源?叉樹

思路及解答

遞歸

采用后序遍歷（左-右-根）的方式遞歸訪問每個節點：

1. 遞歸處理左子樹
2. 遞歸處理右子樹
3. 訪問根節點并交換其左右子樹

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;
}

或者采用前序遍歷（根-左-右）的方式遞歸訪問每個節點：

1. 訪問根節點并交換其左右子樹
2. 遞歸處理左子樹
3. 遞歸處理右子樹

public TreeNode mirrorTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    // 交換左右子樹
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    // 遞歸處理左右子樹
    mirrorTree(root.left);
    mirrorTree(root.right);
    return root;
}

• ?時間復雜度?：O(n)，每個節點只被訪問一次
• ?空間復雜度?：O(h)，h為樹的高度，遞歸棧空間消耗

迭代

利用隊列實現廣度優先搜索(BFS)：

1. 將根節點加入隊列
2. 取出隊首節點并交換其左右子樹
3. 將非空的左右子節點加入隊列
4. 重復直到隊列為空

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();
        // 交換左右子樹
        swap(node);
        // 將子節點加入隊列
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    return root;
}

public void swap(TreeNode root) {
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
}

• 時間復雜度?：O(n)
• ?空間復雜度?：O(n)，最壞情況下需要存儲所有節點