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

题目描述

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

翻转二叉树的意思是：对于树中的每个节点，你都需要交换它的左右子节点。

示例：

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

翻转后：
     4
   /   \
  7     2
 / \   / \
9   6 3   1

解题思路

第一步：理解翻转的本质

翻转二叉树的核心操作很简单：对于每个节点，交换它的左右子树。这个操作需要递归地应用到整棵树的每个节点上。

第二步：基础思路分析

我们可以用递归的思想来解决这个问题：

1. 如果当前节点为空，直接返回空（递归的终止条件）
2. 交换当前节点的左右子节点
3. 递归地翻转左子树
4. 递归地翻转右子树

第三步：递归解法详解

def invertTree(root):
    # 终止条件：如果节点为空，返回None
    if root is None:
        return None
    
    # 交换左右子节点
    root.left, root.right = root.right, root.left
    
    # 递归翻转左子树
    invertTree(root.left)
    # 递归翻转右子树
    invertTree(root.right)
    
    return root

执行过程分析（以上面的示例为例）：

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

第四步：迭代解法（广度优先搜索）

除了递归，我们还可以用层序遍历（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

迭代过程：

1. 将根节点4加入队列
2. 处理节点4：交换左右子节点（2↔7），将7和2加入队列
3. 处理节点7：交换左右子节点（6↔9），将9和6加入队列
4. 处理节点2：交换左右子节点（1↔3），将3和1加入队列
5. 处理剩下的叶子节点（只是交换，没有子节点可加入）

第五步：复杂度分析

• 时间复杂度：O(n)，其中n是树中的节点数，每个节点只被访问一次
• 空间复杂度：
  • 递归解法：O(h)，其中h是树的高度（递归调用栈的深度）
  • 迭代解法：O(w)，其中w是树的最大宽度

第六步：关键要点总结

1. 核心操作：对每个节点，简单交换其左右子节点
2. 遍历方式：可以使用前序、后序或层序遍历，但不能用中序遍历（会导致某些节点被翻转两次）
3. 边界处理：空树的情况需要特殊处理
4. 递归思想：将大树问题分解为子树问题，符合分治策略

这个问题的巧妙之处在于它的简洁性：一个看似复杂的树翻转问题，实际上只需要一个简单的交换操作递归应用到每个节点即可解决。