题解 | 二叉树的镜像

1、解题思路

1. 递归方法：从根节点开始，递归交换每个节点的左右子树。递归终止条件是当前节点为空。
2. 迭代方法（BFS或DFS）：使用栈或队列遍历二叉树。每次取出一个节点，交换其左右子树。将子节点加入栈或队列继续处理。

2、代码实现

C++（递归）

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        // write code here
        if (pRoot == nullptr) {
            return nullptr;
        }

        // 交换左右子树
        TreeNode* tmp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = tmp;

        // 递归处理左右子树
        Mirror(pRoot->left);
        Mirror(pRoot->right);

        return pRoot;
    }
};

C++（迭代）

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <queue>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        // write code here
        if (pRoot == nullptr) {
            return nullptr;
        }

        queue<TreeNode*> q;
        q.push(pRoot);

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            // 交换左右子树
            TreeNode* tmp = node->left;
            node->left = node->right;
            node->right = tmp;

            // 将子节点加入队列
            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }

        return pRoot;
    }
};

Java（递归）

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        if (pRoot == null) return null;

        // 交换左右子树
        TreeNode temp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = temp;

        // 递归处理左右子树
        Mirror(pRoot.left);
        Mirror(pRoot.right);

        return pRoot;
    }
}

Java（迭代）

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        if (pRoot == null) return null;

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(pRoot);

        while (!q.isEmpty()) {
            TreeNode node = q.poll();

            // 交换左右子树
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;

            // 将子节点加入队列
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }

        return pRoot;
    }
}

Python（递归）

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return TreeNode类
#
class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        # write code here
        if not pRoot:
            return None
        
        # 交换左右子树
        pRoot.left, pRoot.right = pRoot.right, pRoot.left
        
        # 递归处理左右子树
        self.Mirror(pRoot.left)
        self.Mirror(pRoot.right)
        
        return pRoot

Python（迭代）

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return TreeNode类
#
from collections import deque

class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        # write code here
        if not pRoot:
            return None
        
        q = deque()
        q.append(pRoot)
        
        while q:
            node = q.popleft()
            
            # 交换左右子树
            node.left, node.right = node.right, node.left
            
            # 将子节点加入队列
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        
        return pRoot

3、复杂度分析

• 时间复杂度：O(n)，每个节点被访问一次。
• 空间复杂度：递归方法为 O(h)（树高），迭代方法为 O(n)（队列存储节点）。