题目描述：
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
解题思路：
方法一：递归（DFS）
核心思路：
翻转整棵树 = 交换每个节点的左右子树
对于任意节点：
交换它的左右子节点
递归翻转左子树
递归翻转右子树
具体过程示例：
4
/ \\
2 7
/ \\ / \\
1 3 6 9
第1步: 交换 4 的左右 → 4 的左=7, 右=2
4
/ \\
7 2
/ \\ / \\
6 9 1 3
第2步: 递归翻转 7 的左右 → 交换 6 和 9
4
/ \\
7 2
/ \\ / \\
9 6 1 3
第3步: 递归翻转 2 的左右 → 交换 1 和 3
4
/ \\
7 2
/ \\ / \\
9 6 3 1 ✅
代码实现：
写法1：前序遍历（最直观）
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return nullptr;
// 交换左右子节点
swap(root->left, root->right);
// 递归翻转左右子树
invertTree(root->left);
invertTree(root->right);
return root;
}
};
写法2：后序遍历
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return nullptr;
// 先递归翻转左右子树
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
// 再交换
root->left = right;
root->right = left;
return root;
}
};
两种写法都可以，前序更直观，后序更符合"先处理子树再处理当前"的思路。
复杂度分析：
| 时间复杂度 | O(n) | 每个节点访问一次 |
| 空间复杂度 | O(h) | 递归栈深度，h 是树的高度 |
空间复杂度说明：
-
最坏情况（链状树）：O(n)
-
平均情况（平衡树）：O(log n)
方法二：迭代法（BFS层序遍历）
思路：
用队列做层序遍历，对每个节点交换左右子节点。
代码实现：
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return nullptr;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
// 交换左右子节点
swap(node->left, node->right);
// 把子节点加入队列
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
return root;
}
};
复杂度分析：
| 时间复杂度 | O(n) | 每个节点访问一次 |
| 空间复杂度 | O(n) | 队列最多存储 n/2 个节点 |
两种方法对比：
| 递归（DFS） | O(n) | O(h) | 简单 | ⭐⭐⭐⭐⭐ |
| 迭代（BFS） | O(n) | O(n) | 中等 | ⭐⭐⭐⭐ |
关键细节：
1. 为什么用 swap？
swap(root->left, root->right);
-
直接交换左右指针，不需要临时变量
-
时间复杂度 O(1)
2. 前序 vs 后序
| 前序 | 先交换，再递归 | 直观 |
| 后序 | 先递归，再交换 | 符合"自底向上" |
两种都可以，前序代码更简洁。
总结：
| 核心思想 | 交换每个节点的左右子树 |
| 递归公式 | swap(left, right); invert(left); invert(right); |
| 时间复杂度 | O(n) |
| 空间复杂度 | O(h)（递归）或 O(n)（迭代） |
