您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# LeetCode中如何翻转二叉树
## 引言
翻转二叉树（Invert Binary Tree）是LeetCode上一道经典的二叉树问题（题目编号226）。它不仅考察了对二叉树结构的理解，也是递归和迭代算法思想的典型应用场景。本文将详细解析翻转二叉树的多种解法，并探讨其时间复杂度和应用场景。
---
## 问题描述
**题目要求**：给定一个二叉树的根节点 `root`，翻转这棵二叉树的所有左右子树，并返回翻转后的根节点。
**示例**：
输入：
4
/
2 7
/ \ /
1 3 6 9
输出：
4
/
7 2
/ \ /
9 6 3 1
---
## 解法一：递归法（DFS）
### 算法思路
递归是最直观的解法，通过深度优先搜索（DFS）遍历二叉树的每个节点，并交换其左右子树。
### 代码实现
```python
def invertTree(root):
if not root:
return None
# 交换左右子树
root.left, root.right = root.right, root.left
# 递归处理左右子树
invertTree(root.left)
invertTree(root.right)
return root
使用广度优先搜索（BFS）逐层遍历二叉树，利用队列存储待处理的节点，依次交换其左右子树。
from collections import deque
def invertTree(root):
if not root:
return None
queue = deque([root])
while queue:
node = queue.popleft()
# 交换左右子树
node.left, node.right = node.right, node.left
# 将子节点加入队列
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
通过栈模拟递归的深度优先搜索，显式地控制遍历顺序。
def invertTree(root):
if not root:
return None
stack = [root]
while stack:
node = stack.pop()
# 交换左右子树
node.left, node.right = node.right, node.left
# 将子节点压入栈
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return root
Morris遍历是一种空间复杂度为O(1)的算法，通过临时修改树的结构实现遍历。
def invertTree(root):
current = root
while current:
if current.left:
# 找到左子树的最右节点
predecessor = current.left
while predecessor.right:
predecessor = predecessor.right
# 将当前节点右子树接到最右节点
predecessor.right = current.right
# 移动左子树到右侧
current.right = current.left
current.left = None
# 移动到右子树（原左子树）
current = current.right
return root
None 时直接返回。| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 递归法 | O(n) | O(h) | 代码简洁 |
| BFS迭代法 | O(n) | O(w) | 层次遍历需求 |
| DFS迭代法 | O(n) | O(h) | 模拟递归过程 |
| Morris遍历 | O(n) | O(1) | 空间限制严格场景 |
根据实际需求选择合适的解法，递归法适合面试快速实现，迭代法更适合工程场景。
”`
（全文约1300字）
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。