在C++中，二叉树镜像反转就是把每个节点的左子树和右子树互换位置。实现方式主要有递归和迭代两种，下面分别给出具体做法与代码示例。
一、二叉树节点定义
无论使用哪种方案，首先都需要定义二叉树的节点结构，代码如下：
// 二叉树节点定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
二、递归方案
递归的思路是：先递归反转左子树，再递归反转右子树，最后交换当前节点的左右指针。代码非常直观。
// 递归实现二叉树镜像反转
void mirrorRecursively(TreeNode* root) {
if (root == nullptr) {
return;
}
// 递归处理左右子树
mirrorRecursively(root->left);
mirrorRecursively(root->right);
// 交换左右孩子
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
}
递归方案分析
- 时间复杂度：每个节点访问一次，为 O(n)
- 空间复杂度：递归调用栈深度取决于树高，最坏情况 O(n)
三、迭代方案
迭代通常使用队列进行层序遍历，每弹出一个节点就交换它的左右子树，再把非空的子节点入队。
#include <queue>
// 迭代实现二叉树镜像反转
void mirrorIteratively(TreeNode* root) {
if (root == nullptr) {
return;
}
std::queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
// 交换当前节点左右孩子
TreeNode* temp = node->left;
node->left = node->right;
node->right = temp;
// 子节点入队
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
}
迭代方案分析
- 时间复杂度：同样遍历所有节点，为 O(n)
- 空间复杂度：队列最大长度接近树的最宽层，最坏 O(n)
四、两种方案如何选择
如果代码简洁性优先且树深度不大，递归写法更易读；若担心递归栈溢出或题目明确要求非递归，则使用迭代写法。两者本质都是遍历并交换，掌握后可灵活应对练习与面试。
注意：文中提到的 <queue> 是C++标准库头文件，实际编译时需包含对应引用。