题目

思路

一句话：对每个节点交换左右孩子，再对左右子树分别做同样的事。

先想最直白的：另建一棵新树，遍历原树时把「原右子树挂到新左、原左子树挂到新右」。这样也能翻，但要额外申请一整棵树的节点、维护新旧两边的指针，代码啰嗦且多花 O(n) 空间——而题目允许原地修改，没必要造新节点。

关键观察：整棵树的翻转不是一个大动作，而是每个局部翻转的组合。把根节点的左右孩子交换，问题就拆成「翻转原来的右子树（现在在左边）」和「翻转原来的左子树（现在在右边）」两个完全同构的小问题。

于是递归定义自然出来：

• 空节点：什么都不做，返回空。
• 非空节点：交换左右孩子 → 递归翻转左子树 → 递归翻转右子树 → 返回当前节点。

先交换再递归就是前序；先递归后交换就是后序，两者都成立。选前序，代码最直观。

下面用示例跟踪局部交换：

每个节点都把自己的两个孩子换位，拼起来就是整棵树的镜像。

解法

递归骨架只有三步：判空、交换、递归。交换用一条语句完成，C++ 可用 swap，Python 用元组同时赋值。

下图把上面 3 个步骤串成流程，并逐步演示：

C++

class Solution {
public:
 TreeNode* invertTree(TreeNode* root) {
 if (root == nullptr) {
 return nullptr;          // 递归出口：空树仍为空
 }
 swap(root->left, root->right);   // 先交换当前节点的左右孩子
 invertTree(root->left)
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。