我来给你讲解 LeetCode 第 226 题「翻转二叉树」。

题目描述

给你一棵二叉树的根节点 root，你需要翻转这棵二叉树，并返回翻转后的根节点。

翻转二叉树的定义：将二叉树中每个节点的左右子节点互换位置。

示例：

输入：
     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：
     4
   /   \
  7     2
 / \   / \
9   6 3   1

解题思路分析

关键观察

1. 翻转操作需要作用在每个节点上
2. 对于每个节点，只需要交换它的左右子节点
3. 翻转完当前节点后，需要继续翻转它的左右子树
4. 这是一个典型的递归问题，也可以用迭代方式解决

方法选择

• 递归法：代码简洁，易于理解
• 迭代法（BFS/DFS）：需要显式使用栈或队列

解题步骤详解

方法一：递归法（前序遍历）

步骤分解：

1. 基准情况：如果当前节点为 null，直接返回 null
2. 交换操作：交换当前节点的左右子节点
3. 递归翻转：
   • 递归翻转左子树
   • 递归翻转右子树
4. 返回结果：返回当前节点

代码实现：

def invertTree(root):
    # 步骤1：基准情况
    if not root:
        return None
    
    # 步骤2：交换左右子节点
    root.left, root.right = root.right, root.left
    
    # 步骤3：递归翻转子树
    invertTree(root.left)
    invertTree(root.right)
    
    # 步骤4：返回当前节点
    return root

执行过程示例（以示例二叉树为例）：

1. 从根节点4开始，交换节点2和7
2. 递归处理新的左子树（原右子树7）：
   • 节点7交换节点6和9
   • 递归处理节点6（叶子节点，直接返回）
   • 递归处理节点9（叶子节点，直接返回）
3. 递归处理新的右子树（原左子树2）：
   • 节点2交换节点1和3
   • 递归处理节点1（叶子节点，直接返回）
   • 递归处理节点3（叶子节点，直接返回）

方法二：迭代法（BFS层次遍历）

步骤分解：

1. 边界检查：如果根节点为空，直接返回
2. 初始化队列：将根节点加入队列
3. 遍历队列：
   • 弹出当前节点
   • 交换当前节点的左右子节点
   • 如果左子节点存在，加入队列
   • 如果右子节点存在，加入队列
4. 返回结果：返回根节点

代码实现：

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

复杂度分析

• 时间复杂度：O(n)，每个节点恰好被访问一次
• 空间复杂度：
  • 递归法：O(h)，h为树的高度（递归栈空间）
  • 迭代法：O(n)，最坏情况下队列需要存储所有叶子节点

关键要点总结

1. 核心操作：交换每个节点的左右子节点
2. 遍历顺序：前序、后序、层次遍历都可以，但中序遍历需要小心处理
3. 边界处理：空树情况要特殊处理
4. 递归终止条件：遇到空节点时返回

这个题目很好地体现了树遍历的基本思想，是理解二叉树操作的经典入门题目。