LeetCode 226. 翻转二叉树 详细技术解析（CSDN版）

LeetCode 226. 翻转二叉树 详细技术解析（CSDN版）

题目概述（Problem Statement）

给定一棵二叉树的根节点 root，要求翻转这棵二叉树（即交换每一个节点的左子树和右子树），最终返回翻转后二叉树的根节点。

核心规则

• 翻转逻辑：对树中的每一个节点，交换其左孩子和右孩子，递归或迭代执行该操作，直至所有节点都完成翻转；

• 边界情况：若二叉树为空（root = None），直接返回空；单个节点的二叉树，翻转后仍为自身；

• 返回值：翻转后二叉树的根节点（与原根节点地址一致，仅左右子树结构发生变化）。

示例提示

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

解释：原二叉树根节点为4，左子树为2（左1、右3），右子树为7（左6、右9）；翻转后，根节点仍为4，左子树变为7（左9、右6），右子树变为2（左3、右1）。

示例2：输入 root = [2,1,3] → 输出 [2,3,1]

解释：根节点2的左子树1、右子树3交换，翻转后左子树为3，右子树为1。

示例3：输入 root = [] → 输出 []

解释：空树翻转后仍为空。

问题分析（Problem Analysis）

核心难点

1. 遍历逻辑：需确保所有节点的左右子树都被交换，不遗漏任何一个节点（包括叶子节点的空孩子）；

2. 递归与迭代的选择：两种方式均可实现，但需理解两种思路的底层逻辑，避免递归栈溢出（本题节点数≤100，递归无压力）；

3. 边界处理：空树、单个节点、只有左子树/只有右子树的场景，需确保代码能正常处理，不出现空指针异常。

关键思路

翻转二叉树的本质是「后序遍历」或「前序遍历」的应用——先处理子节点，再交换当前节点的左右子树（后序），或先交换当前节点的左右子树，再处理子节点（前序），两种思路均可实现完整翻转。

1. 递归思路（推荐入门）：

   • 终止条件：当前节点为None（空节点），直接返回None；

   • 递归逻辑：先递归翻转当前节点的左子树，再递归翻转当前节点的右子树；

   • 核心操作：交换当前节点的左子树和右子树，返回当前节点（作为父节点的子节点）。

2. 迭代思路（工业级常用，避免递归栈溢出）：

   • 使用队列（或栈）存储待处理的节点，模拟递归的遍历顺序；

   • 循环处理：取出队列头部节点，交换其左右子树，再将左右子节点（非空）加入队列；

   • 终止条件：队列为空，所有节点处理完毕。

技术选型与优化点

• 数据结构：递归无需额外数据结构，迭代使用队列（FIFO，符合层序遍历逻辑）或栈（LIFO，符合前序遍历逻辑）；

• 遍历方式：前序/后序递归代码简洁，适合入门；迭代方式更稳定，适合节点数较多的场景（本题节点数少，两种均可）；

• 时间复杂度：O(n)，n为二叉树节点数，每个节点仅被访问和交换一次；

• 空间复杂度：递归为O(h)（h为树的高度，最坏情况为链表，h=n）；迭代为O(n)（队列最多存储一层节点，最坏情况为满二叉树的最后一层，节点数≈n/2）。

完整代码实现（Python）

提供「递归版」（简洁易懂，推荐入门）和「迭代版」（工业级稳定）两种实现，均严格贴合题目要求的代码格式，包含详细注释：

版本1：递归版（推荐）

fromtypingimportOptional# Definition for a binary tree node.classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=val self.left=left self.right=rightclassSolution:definvertTree(self,root:Optional[TreeNode])->Optional[TreeNode]:# 终止条件：当前节点为空，直接返回空（递归出口）ifnotroot:returnNone# 1. 递归翻转左子树，返回翻转后的左子树根节点left_inverted=self.invertTree(root.left)# 2. 递归翻转右子树，返回翻转后的右子树根节点right_inverted=self.invertTree(root.right)# 3. 交换当前节点的左、右子树（核心操作）root.left=right_inverted root.right=left_inverted# 4. 返回当前节点（作为父节点的子节点，完成递归回溯）returnroot

版本2：迭代版（层序遍历，稳定无栈溢出）

fromtypingimportOptionalfromcollectionsimportdeque# Definition for a binary tree node.classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=val self.left=left self.right=rightclassSolution:definvertTree(self,root:Optional[TreeNode])->Optional[TreeNode]:# 边界条件：空树直接返回ifnotroot:returnNone# 初始化队列，存入根节点（待处理节点）queue=deque([root])# 循环处理队列中的所有节点whilequeue:# 取出队列头部节点（当前待处理节点）current_node=queue.popleft()# 交换当前节点的左、右子树（核心操作）# 无需判断子节点是否为空，空节点交换后仍为空current_node.left,current_node.right=current_node.right,current_node.left# 将交换后的左子节点加入队列（非空才加入，避免无效处理）ifcurrent_node.left:queue.append(current_node.left)# 将交换后的右子节点加入队列ifcurrent_node.right:queue.append(current_node.right)# 根节点未改变，返回翻转后的根节点returnroot

代码解析（Code Explanation）

1. 递归版代码解析

• 终止条件：if not root: return None，当遍历到空节点时，无需翻转，直接返回空，作为递归的出口；

• 递归过程：先递归处理左子树和右子树，确保子树先完成翻转，再交换当前节点的左右子树，避免子树未翻转就交换导致逻辑混乱；

• 核心操作：root.left, root.right = right_inverted, left_inverted，交换翻转后的左右子树，完成当前节点的翻转；

• 回溯返回：返回当前节点，供父节点交换左右子树使用，形成完整的递归回溯流程。

2. 迭代版代码解析

• 边界处理：空树直接返回None，避免队列初始化报错；

• 队列初始化：使用deque（高效队列）存储待处理节点，初始存入根节点；

• 循环处理：

  • 取出队列头部节点，交换其左右子树（即使子节点为空，交换后仍为空，不影响逻辑）；

  • 将交换后的左右子节点（非空）加入队列，确保后续继续处理子节点的翻转；

• 返回根节点：翻转过程中仅修改节点的左右子树，根节点地址不变，直接返回即可。

3. 边界情况处理

• 空树（root = None）：直接返回None，两种版本均能正确处理；

• 单个节点（无左右子树）：交换左右子树（均为空），返回自身，符合预期；

• 只有左子树/只有右子树：交换后，原左子树变为右子树，原右子树（空）变为左子树，逻辑正确；

• 满二叉树（如示例1）：递归/迭代均能逐层翻转，确保所有节点的左右子树都被交换。

测试案例验证（Test Case Verification）

示例1：满二叉树翻转

# 输入：root = [4,2,7,1,3,6,9]（二叉树结构）# 4# / \# 2 7# / \ / \# 1 3 6 9# 执行递归版流程：1.递归处理4的左子树（2），再处理2的左子树（1），1无左右子树，返回1；2.处理2的右子树（3），3无左右子树，返回3；交换2的左右子树，2的左=3，右=1；3.递归处理4的右子树（7），再处理7的左子树（6），返回6；处理7的右子树（9），返回9；交换7的左右子树，7的左=9，右=6；4.交换4的左右子树，4的左=7，右=2；# 翻转后结构：# 4# / \# 7 2# / \ / \# 9 6 3 1# 输出：[4,7,2,9,6,3,1]（与示例一致）

示例2：简单二叉树翻转

# 输入：root = [2,1,3]# 2# / \# 1 3# 执行迭代版流程：1.队列初始化：[2]；2.取出2，交换左右子树（左=3，右=1），将3、1加入队列；3.取出3，无左右子树，不加入队列；4.取出1，无左右子树，不加入队列；5.队列为空，结束；# 翻转后结构：# 2# / \# 3 1# 输出：[2,3,1]（与示例一致）

示例3：空树验证

# 输入：root = []# 递归版：直接返回None；# 迭代版：队列初始化为空，循环不执行，返回None；# 输出：[]（与示例一致）

性能分析（Performance Analysis）

• 时间复杂度：两种版本均为O(n)，n为二叉树节点数，每个节点仅被访问1次，交换操作为O(1)，整体效率极高；

• 空间复杂度：

  • 递归版：O(h)，h为树的高度。最好情况（完全二叉树）h=log₂n，最坏情况（链表）h=n；

  • 迭代版：O(n)，队列最多存储一层节点，最坏情况（满二叉树最后一层）节点数为n/2，空间开销稳定。

• 优化点：递归版代码简洁，适合面试快速编写；迭代版无递归栈溢出风险，适合大规模二叉树，实际项目中更推荐使用迭代版。

常见错误与避坑指南（Common Mistakes）

1. 递归终止条件缺失：忘记判断if not root: return None，会导致递归无限调用，最终报栈溢出错误；

2. 交换顺序错误：先交换当前节点的左右子树，再递归处理子树，会导致子树被重复翻转，最终结果错误（正确顺序：先递归子树，再交换当前节点）；

3. 迭代版队列操作错误：使用列表模拟队列（用append和pop(0)），时间复杂度会变为O(n²)（pop(0)为O(n)），推荐使用collections.deque的popleft()（O(1)）；

4. 空节点处理遗漏：迭代版中，将子节点加入队列时未判断是否为空，会导致队列中存入空节点，增加无效循环（虽不影响结果，但降低效率）；

5. 误解返回值：认为翻转后根节点会改变，试图创建新的根节点，实际翻转仅修改节点的左右子树，根节点地址不变，直接返回原根节点即可。

总结（Summary）

本题是二叉树遍历的经典应用，核心逻辑是「交换每个节点的左右子树」，递归和迭代两种方式均可实现，重点在于理解遍历顺序和边界处理。

核心收获：

• 掌握二叉树的递归/迭代遍历思路，理解递归回溯的过程；

• 学会处理二叉树的边界情况（空树、单个节点等），避免空指针异常；

• 区分递归与迭代的优劣，根据场景选择合适的实现方式。

本题难度简单，适合二叉树入门练习，其核心思路（遍历+节点操作）可迁移到其他二叉树题目（如二叉树的镜像、对称二叉树等），是掌握二叉树操作的基础。

扩展思考（Extension）

• 如何用前序遍历实现翻转二叉树？（提示：先交换当前节点左右子树，再递归处理左右子树）；

• 如何翻转二叉树的指定层（如仅翻转第2层节点的左右子树）？（提示：层序遍历定位到指定层，仅交换该层节点的左右子树）；

• 如何判断两棵二叉树是否互为翻转（镜像）？（提示：同时遍历两棵树，判断对应节点的值是否相等，且左节点对应右节点、右节点对应左节点）。