LeetCode 热题100 226. 翻转二叉树

LeetCode 热题100 | 226. 翻转二叉树

大家好，今天我们来解决一道经典的算法题——翻转二叉树。这道题在 LeetCode 上被标记为简单难度，要求我们翻转一棵二叉树，并返回其根节点。下面我将详细讲解解题思路，并附上 Python 代码实现。

---

题目描述

给定一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。

示例：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

---

解题思路

翻转二叉树的核心思想是交换每个节点的左右子树。我们可以通过递归或迭代的方式来实现。

核心思想

1. 递归法：

   • 递归地翻转左子树和右子树。
   • 交换当前节点的左右子树。

2. 迭代法（BFS）：

   • 使用队列进行层次遍历，逐层交换每个节点的左右子树。

---

代码实现

方法 1：递归法

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef invertTree(root):""":type root: TreeNode:rtype: TreeNode"""if not root:return None# 递归翻转左右子树left = invertTree(root.left)right = invertTree(root.right)# 交换当前节点的左右子树root.left = rightroot.right = leftreturn root

方法 2：迭代法（BFS）

from collections import dequedef invertTree(root):""":type root: TreeNode:rtype: TreeNode"""if not root:return Nonequeue = 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

---

代码解析

递归法

1. 递归终止条件：

   • 如果当前节点为空，返回 None。

2. 递归翻转左右子树：

   • 递归地翻转左子树和右子树。

3. 交换当前节点的左右子树：

   • 将当前节点的左子树指向翻转后的右子树，右子树指向翻转后的左子树。

4. 返回根节点：

   • 返回翻转后的二叉树的根节点。

迭代法（BFS）

1. 初始化：

   • 如果根节点为空，直接返回 None。
   • 使用队列存储节点，初始时将根节点加入队列。

2. 遍历队列：

   • 弹出当前节点，交换其左右子树。
   • 将当前节点的左右子节点加入队列。

3. 返回根节点：

   • 遍历结束后，返回翻转后的二叉树的根节点。

---

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
• 空间复杂度：
  • 递归法：O(h)，其中 h 是二叉树的高度，递归调用栈的深度为树的高度。
  • 迭代法：O(n)，队列的最大空间为树的宽度。

---

示例运行

示例 1

# 创建二叉树 [4,2,7,1,3,6,9]
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)# 翻转二叉树
inverted_root = invertTree(root)# 层序遍历输出结果
def levelOrder(root):if not root:return []result = []queue = deque([root])while queue:level_size = len(queue)level_nodes = []for _ in range(level_size):node = queue.popleft()level_nodes.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)result.append(level_nodes)return resultprint(levelOrder(inverted_root))  # 输出: [[4], [7, 2], [9, 6, 3, 1]]

示例 2

# 创建二叉树 [2,1,3]
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)# 翻转二叉树
inverted_root = invertTree(root)# 层序遍历输出结果
print(levelOrder(inverted_root))  # 输出: [[2], [3, 1]]

示例 3

# 创建空二叉树 []
root = None# 翻转二叉树
inverted_root = invertTree(root)# 层序遍历输出结果
print(levelOrder(inverted_root))  # 输出: []

---

总结

通过递归或迭代的方式，我们可以高效地翻转二叉树。递归法代码简洁，但可能受递归深度限制；迭代法使用队列进行层次遍历，适合处理较大的树。希望这篇题解对你有帮助！如果还有其他问题，欢迎继续提问！

关注我，获取更多算法题解和编程技巧！