C++如何实现二叉树的镜像翻转 原地左右节点交换

镜像翻转既可用递归也可用迭代，二者本质均为深度优先遍历；必须访问每个节点并交换其left和right指针，空指针交换安全，无需前置判空，但递归/迭代的继续条件需判空，漏判会导致部分子树未处理。

镜像翻转必须递归还是能用迭代？

能用迭代，但递归更直观、不易出错。关键不是选哪种方式，而是必须访问每个节点并交换其 left 和 right 指针——无论用栈模拟递归，还是直接递归，本质都是深度优先遍历（DFS）。

常见错误是只翻转某一层或漏掉空节点处理。比如写成 if (root->left) swap(...)，会跳过 left 为空但 right 非空的情况，导致部分子树没被处理。

• 递归写法：函数签名通常为 void mirror(TreeNode* root)，入口判空后直接递归左右子树
• 迭代写法：用 stack<treenode></treenode> 或 queue<treenode></treenode>，每次取节点后交换其左右指针，再把非空子节点压栈/入队
• 注意：交换前要先保存 root->left，否则 root->right 赋值后原左子树丢失（不能写成 root->left = root->right; root->right = root->left;）

交换时要不要检查子节点是否为空？

完全不用检查。交换 left 和 right 指针本身是安全操作，空指针交换无副作用。真正需要判空的是递归/迭代的继续条件，不是交换动作本身。

典型错误示例：if (root && root->left && root->right) swap(root->left, root->right); —— 这样只翻转了两个子节点都存在的节点，叶子节点和单子树节点全被跳过。

立即学习“C++免费学习笔记（深入）”；

• 正确做法：只要 root 非空，就交换 root->left 和 root->right，然后递归处理这两个指针指向的子树（即使它们是 nullptr）
• 迭代中同理：入栈/入队前不检查子节点是否为空，交换后再决定是否把子节点加入容器

为什么不能只改值而要改指针？

因为“镜像翻转”定义的是结构变换，不是数据重排。题目要求“原地左右节点交换”，即改变树的拓扑关系，而非把所有值收集排序再重建。改值（如交换 val）得到的是值对称，不是结构镜像。

例如输入树：

    1   /   2   3 /4

，镜像后应为

    1   /   3   2     /    4

。若只交换 val，结果仍是三叉结构，但左子树仍含 2 和 4，不符合题意。

• swap(root->left, root->right) 是必须的，swap(root->val, ...) 完全无关
• 如果节点含额外字段（如 height 或 size），这些字段不会自动更新，需手动维护或重新计算

LeetCode 226 题常见运行时错误怎么定位？

最常触发的是 member access within null pointer，对应代码里写了类似 root->left->val 却没提前判 root->left 是否为空。镜像翻转本身不访问 val，但调试时加的日志或后续验证逻辑容易踩坑。

• 确保所有对 -> 的使用前都有显式空检查，或用智能指针（如 std::unique_ptr）配合 get() 显式判空
• 递归终止条件必须是 if (!root) return;，不能写成 if (root == nullptr) 以外的形式（虽等价，但易漏写）
• 提交前用极端 case 验证：空树、单节点、只有左链、只有右链

真正容易被忽略的点是：翻转后原根节点的 left 和 right 已互换，但它的父节点指针没变——这没问题，因为镜像是以当前树为整体进行的，无需向上回溯修正父引用。