226. 翻转二叉树
题目描述
输入二叉树的根节点 root。把树左右镜像翻转：每个节点的左子树和右子树互换。
返回翻转后的根节点。空树返回 null。树以层序数组表示。
示例 1
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
解释：每一层的节点顺序都左右颠倒了。
示例 2
输入：root = [2,1,3] 输出：[2,3,1]
解释：根的两个孩子 1 和 3 互换位置。
示例 3
输入：root = [] 输出：[]
解释：空树翻转后仍为空。
数据范围
- 节点数在
[0, 100]范围内。 -100 <= Node.val <= 100
解题思路：递归（前序交换左右子树）
先交换当前节点的左右孩子，再递归翻转交换后的两棵子树。
为什么正确
调用返回时，当前子树中的每个节点都完成左右交换。
复杂度分析
时间 O(n)，递归栈 O(h)；h 为树高，最坏可为 n；Python 递归受解释器递归深度限制，深链树应改用显式栈。
易错点
翻转要处理每个节点，不能只交换根节点的两个孩子。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def invertTree(self, root):
if root is None:
return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return rootclass Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = root.left; root.left = root.right; root.right = left;
invertTree(root.left);
invertTree(root.right);
return root;
}
}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;
}
};func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
root.Left, root.Right = root.Right, root.Left
invertTree(root.Left)
invertTree(root.Right)
return root
}var invertTree = function(root) {
if (root === null) {
return null;
}
[root.left, root.right] = [root.right, root.left];
invertTree(root.left);
invertTree(root.right);
return root;
};function invertTree(root: TreeNode | null): TreeNode | null {
if (root === null) {
return null;
}
[root.left, root.right] = [root.right, root.left];
invertTree(root.left);
invertTree(root.right);
return root;
}其他解法
翻转只要求每个结点都交换一次左右孩子，与访问顺序无关。递归借用调用栈做深度优先遍历，空间取决于树高；BFS 用队列逐层遍历，空间取决于树宽。
解法 2：广度优先搜索（迭代） 时间 O(n)，空间 O(n)
用队列按层遍历所有结点。每取出一个结点，就交换它的左右孩子，再把非空的孩子放入队列。每个结点都恰好被交换一次，遍历结束后整棵树就翻转了。
没有递归，树退化成链时也不会栈溢出。需要显式维护队列，代码比递归长；队列大小取决于最宽的一层。
from collections import deque
from typing import Optional
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return None
q = deque([root])
while q:
node = q.popleft()
node.left, node.right = node.right, node.left
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return rootclass Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode node = q.poll();
TreeNode t = node.left;
node.left = node.right;
node.right = t;
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
return root;
}
}class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (!root) 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;
}
};func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
q := []*TreeNode{root}
for len(q) > 0 {
node := q[0]
q = q[1:]
node.Left, node.Right = node.Right, node.Left
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
return root
}var invertTree = function(root) {
if (!root) return null;
const q = [root];
for (let i = 0; i < q.length; i++) {
const node = q[i];
[node.left, node.right] = [node.right, node.left];
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
return root;
};function invertTree(root: TreeNode | null): TreeNode | null {
if (!root) return null;
const q: TreeNode[] = [root];
for (let i = 0; i < q.length; i++) {
const node = q[i];
[node.left, node.right] = [node.right, node.left];
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
return root;
};