LeetCode 226. 翻转二叉树｜Python 解法详解

LeetCode 226. 翻转二叉树｜Python 解法详解

CSDN 算法专题 · 二叉树 | 难度：简单

题目信息

• 题号：226
• 难度：简单
• LeetCode：题目链接

题目描述

交换二叉树中每个节点的左右子树，返回翻转后的根节点。

示例

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

约束

节点数不超过 100。

解题思路

核心观察

每个节点都执行同一操作：交换左右孩子，再递归处理交换后的两棵子树。空节点是递归边界。前序或后序实现都可以。

推导与执行步骤

1. 空节点返回 None
2. 交换当前节点左右孩子
3. 递归翻转左右子树
4. 返回当前节点

为什么这个方法正确

算法始终围绕上述核心观察维护有效状态，并且每一步只排除已经能够证明不可能产生更优答案的情况。按照执行步骤处理后，所有可能影响答案的元素或节点都会被恰好检查，因此不会遗漏合法答案；状态更新又严格遵守题目约束，所以最终结果有效。

从边界看，空区间、单个元素、全部相同或完全不匹配等情况都会落入初始化条件或循环终止条件，不需要依赖未定义状态。实现时再重点检查下标、空节点和重复元素，即可保证算法在极端输入下仍然成立。

Python 代码

# 解法核心：每个节点都执行同一操作：交换左右孩子，再递归处理交换后的两棵子树。空节点是递归边界。前序或后序实现都可以。# 实现步骤：# 1. 空节点返回 None# 2. 交换当前节点左右孩子# 3. 递归翻转左右子树# 4. 返回当前节点fromtypingimportOptionalclassTreeNode: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(root.left,root.right)=(root.right,root.left)self.invertTree(root.left)self.invertTree(root.right)returnroot

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(h)

易错点

交换后递归的对象已经互换，但只要两边都处理就不会遗漏。

总结

这道题的关键是：每个节点都执行同一操作：交换左右孩子，再递归处理交换后的两棵子树。理解这一点后，再结合边界条件检查，代码就能保持清晰且稳定。