翻转二叉树
给你一棵二叉树的根节点 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 = []
输出：[]
提示：
- 树中节点数目范围在
[0, 100]内 -100 <= Node.val <= 100
解法一（递归 DFS）：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
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;
}
};
解法二（迭代层序遍历）：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
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 != nullptr)
{
q.push(node->left);
}
if (node->right != nullptr)
{
q.push(node->right);
}
}
return root;
}
};
核心思想
翻转一棵二叉树，本质上不是改变节点的值，而是改变每个节点的左右指针。
对于任意一个节点来说，只需要做一件事：
交换它的左孩子和右孩子
然后继续对它的左右子树做同样的事情。
这题最关键的观察是：
整棵树翻转完成，当且仅当每个节点的左右子树都完成交换。
因为二叉树本身是递归结构，所以递归解法很自然。
如果不用递归，也可以遍历整棵树。无论用层序遍历还是栈遍历，只要保证每个节点都被访问一次，并在访问时交换左右孩子，就能完成翻转。
解法一：递归 DFS
递归函数 invertTree(root) 表示：
翻转以 root 为根的整棵子树，并返回 root
如果 root == nullptr，说明当前子树为空，直接返回 nullptr。
否则先交换当前节点的左右孩子：
swap(root->left, root->right);
交换之后，原来的右子树到了左边，原来的左子树到了右边。
接着继续翻转交换后的左右子树：
invertTree(root->left);
invertTree(root->right);
最后返回当前根节点：
return root;
为什么可以先交换再递归
对一个节点来说，翻转要求它的左右子树互换位置。
至于子树内部的节点，也需要继续完成同样的左右交换。
所以可以有两种顺序：
- 先翻转左右子树，再交换当前节点的左右孩子
- 先交换当前节点的左右孩子，再分别翻转新的左右子树
两种写法都可以。
当前代码采用的是先交换，再递归。
因为交换后，root->left 和 root->right 仍然分别指向两棵需要继续翻转的子树。
只要两边都递归处理一次，就不会遗漏任何节点。
解法二：迭代层序遍历
递归本质上是遍历整棵树。
如果不用递归，可以用队列做层序遍历。
初始时把根节点放入队列：
q.push(root);
每次从队列中取出一个节点：
TreeNode* node = q.front();
q.pop();
交换它的左右孩子：
swap(node->left, node->right);
然后把非空孩子加入队列，等待后续处理：
if (node->left != nullptr)
{
q.push(node->left);
}
if (node->right != nullptr)
{
q.push(node->right);
}
注意这里加入的是交换之后的左右孩子。
这不影响正确性，因为无论它们原来在左边还是右边，只要每个节点最终都被访问并交换一次即可。
边界情况
如果二叉树为空：
root = []
直接返回 nullptr。
如果二叉树只有一个节点：
root = [1]
它没有左右孩子，交换后仍然是自己。
如果某个节点只有左孩子或只有右孩子，交换后这个孩子会移动到另一侧。
例如：
root = [1,null,2]
翻转后变成：
root = [1,2]
正确性证明
我们证明：两个解法都能正确返回翻转后的二叉树。
结论 1：递归解法能正确翻转任意子树
对于空子树，算法直接返回 nullptr，翻转结果仍然是空树，正确。
对于非空子树，算法先交换当前根节点的左右孩子。
这一步保证当前节点的左右位置满足翻转要求。
然后算法递归翻转交换后的左子树和右子树。
根据递归含义，这两棵子树内部也会被正确翻转。
因此，以当前节点为根的整棵子树都会被正确翻转。
结论 2：递归解法不会遗漏节点
每个非空节点在递归调用中都会执行一次左右孩子交换。
当前节点交换后，算法继续递归处理 root->left 和 root->right。
这两棵子树包含了当前节点下面的所有后代节点。
所以所有节点都会被访问并交换一次，不会遗漏。
结论 3：迭代解法会访问每个节点一次
迭代解法从根节点开始，把节点放入队列。
每次取出一个节点后，会把它的非空孩子继续加入队列。
因为二叉树中每个非根节点都只会作为某个父节点的孩子被加入队列一次，所以每个节点都会被访问一次。
结论 4：迭代解法访问节点时完成了该节点的翻转
对于每个被队列取出的节点，算法都会执行：
swap(node->left, node->right);
这正好完成了该节点左右孩子的交换。
由结论 3 可知，每个节点都会被访问一次。
所以整棵树中每个节点的左右孩子都会被交换一次。
得出结论
由结论 1 和结论 2 可知，递归 DFS 解法正确。
由结论 3 和结论 4 可知，迭代层序遍历解法正确。
因此两个解法都能正确返回翻转后的二叉树根节点。
举例理解
以：
root = [4,2,7,1,3,6,9]
为例，原树是：
4
/ \
2 7
/ \ / \
1 3 6 9
从根节点开始交换：
- 节点
4的左右孩子交换，2和7换位置 - 节点
2的左右孩子交换，1和3换位置 - 节点
7的左右孩子交换，6和9换位置
翻转后变成：
4
/ \
7 2
/ \ / \
9 6 3 1
所以层序结果是：
[4,7,2,9,6,3,1]
复杂度分析
设二叉树节点数为 n，树的高度为 h。
解法一
每个节点都会被递归访问一次。
- 时间复杂度：
O(n) - 空间复杂度：
O(h)
空间复杂度来自递归调用栈。
解法二
每个节点入队一次、出队一次。
- 时间复杂度：
O(n) - 空间复杂度：
O(n)
队列在最宽的一层可能保存 O(n) 个节点。
如果想写得最简洁，递归解法更推荐；如果不想使用递归，可以使用层序遍历。