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核心难点遍历逻辑需确保所有节点的左右子树都被交换不遗漏任何一个节点包括叶子节点的空孩子递归与迭代的选择两种方式均可实现但需理解两种思路的底层逻辑避免递归栈溢出本题节点数≤100递归无压力边界处理空树、单个节点、只有左子树/只有右子树的场景需确保代码能正常处理不出现空指针异常。关键思路翻转二叉树的本质是「后序遍历」或「前序遍历」的应用——先处理子节点再交换当前节点的左右子树后序或先交换当前节点的左右子树再处理子节点前序两种思路均可实现完整翻转。递归思路推荐入门终止条件当前节点为None空节点直接返回None递归逻辑先递归翻转当前节点的左子树再递归翻转当前节点的右子树核心操作交换当前节点的左子树和右子树返回当前节点作为父节点的子节点。迭代思路工业级常用避免递归栈溢出使用队列或栈存储待处理的节点模拟递归的遍历顺序循环处理取出队列头部节点交换其左右子树再将左右子节点非空加入队列终止条件队列为空所有节点处理完毕。技术选型与优化点数据结构递归无需额外数据结构迭代使用队列FIFO符合层序遍历逻辑或栈LIFO符合前序遍历逻辑遍历方式前序/后序递归代码简洁适合入门迭代方式更稳定适合节点数较多的场景本题节点数少两种均可时间复杂度O(n)n为二叉树节点数每个节点仅被访问和交换一次空间复杂度递归为O(h)h为树的高度最坏情况为链表hn迭代为O(n)队列最多存储一层节点最坏情况为满二叉树的最后一层节点数≈n/2。完整代码实现Python提供「递归版」简洁易懂推荐入门和「迭代版」工业级稳定两种实现均严格贴合题目要求的代码格式包含详细注释版本1递归版推荐fromtypingimportOptional# Definition for a binary tree node.classTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightrightclassSolution:definvertTree(self,root:Optional[TreeNode])-Optional[TreeNode]:# 终止条件当前节点为空直接返回空递归出口ifnotroot:returnNone# 1. 递归翻转左子树返回翻转后的左子树根节点left_invertedself.invertTree(root.left)# 2. 递归翻转右子树返回翻转后的右子树根节点right_invertedself.invertTree(root.right)# 3. 交换当前节点的左、右子树核心操作root.leftright_inverted root.rightleft_inverted# 4. 返回当前节点作为父节点的子节点完成递归回溯returnroot版本2迭代版层序遍历稳定无栈溢出fromtypingimportOptionalfromcollectionsimportdeque# Definition for a binary tree node.classTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightrightclassSolution:definvertTree(self,root:Optional[TreeNode])-Optional[TreeNode]:# 边界条件空树直接返回ifnotroot:returnNone# 初始化队列存入根节点待处理节点queuedeque([root])# 循环处理队列中的所有节点whilequeue:# 取出队列头部节点当前待处理节点current_nodequeue.popleft()# 交换当前节点的左、右子树核心操作# 无需判断子节点是否为空空节点交换后仍为空current_node.left,current_node.rightcurrent_node.right,current_node.left# 将交换后的左子节点加入队列非空才加入避免无效处理ifcurrent_node.left:queue.append(current_node.left)# 将交换后的右子节点加入队列ifcurrent_node.right:queue.append(current_node.right)# 根节点未改变返回翻转后的根节点returnroot代码解析Code Explanation1. 递归版代码解析终止条件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的左子树11无左右子树返回12.处理2的右子树33无左右子树返回3交换2的左右子树2的左3右13.递归处理4的右子树7再处理7的左子树6返回6处理7的右子树9返回9交换7的左右子树7的左9右64.交换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为树的高度。最好情况完全二叉树hlog₂n最坏情况链表hn迭代版O(n)队列最多存储一层节点最坏情况满二叉树最后一层节点数为n/2空间开销稳定。优化点递归版代码简洁适合面试快速编写迭代版无递归栈溢出风险适合大规模二叉树实际项目中更推荐使用迭代版。常见错误与避坑指南Common Mistakes递归终止条件缺失忘记判断if not root: return None会导致递归无限调用最终报栈溢出错误交换顺序错误先交换当前节点的左右子树再递归处理子树会导致子树被重复翻转最终结果错误正确顺序先递归子树再交换当前节点迭代版队列操作错误使用列表模拟队列用append和pop(0)时间复杂度会变为O(n²)pop(0)为O(n)推荐使用collections.deque的popleft()O(1)空节点处理遗漏迭代版中将子节点加入队列时未判断是否为空会导致队列中存入空节点增加无效循环虽不影响结果但降低效率误解返回值认为翻转后根节点会改变试图创建新的根节点实际翻转仅修改节点的左右子树根节点地址不变直接返回原根节点即可。总结Summary本题是二叉树遍历的经典应用核心逻辑是「交换每个节点的左右子树」递归和迭代两种方式均可实现重点在于理解遍历顺序和边界处理。核心收获掌握二叉树的递归/迭代遍历思路理解递归回溯的过程学会处理二叉树的边界情况空树、单个节点等避免空指针异常区分递归与迭代的优劣根据场景选择合适的实现方式。本题难度简单适合二叉树入门练习其核心思路遍历节点操作可迁移到其他二叉树题目如二叉树的镜像、对称二叉树等是掌握二叉树操作的基础。扩展思考Extension如何用前序遍历实现翻转二叉树提示先交换当前节点左右子树再递归处理左右子树如何翻转二叉树的指定层如仅翻转第2层节点的左右子树提示层序遍历定位到指定层仅交换该层节点的左右子树如何判断两棵二叉树是否互为翻转镜像提示同时遍历两棵树判断对应节点的值是否相等且左节点对应右节点、右节点对应左节点。