翻转二叉树

问题拆解

翻转的效果是让整棵树沿中轴左右镜像。乍看要动到每一层的每个节点，似乎很繁琐，但只要盯住根节点就会发现：翻转整棵树，无非是把根的左右孩子交换，然后让换过去的两棵子树各自也完成翻转。

这是一个可以原地递归下去的操作——每一层都只做「交换 + 下探」这一件事。

一个看似要动全局的变换，往往能拆成「当前层做一步，剩下的交给子问题」。

交换后递归

def invertTree(root):
    if not root:
        return None
    root.left, root.right = root.right, root.left
    invertTree(root.left)
    invertTree(root.right)
    return root

Python 的元组赋值让交换一行搞定,不需要临时变量。先交换还是先递归其实都行:因为交换只影响当前节点的两个指针,不改变子树内部结构,两种顺序得到的结果一致。空树直接返回,是递归自然收口的地方。

如果不想用递归栈,也可以借助一个队列做层序遍历,对每个出队的节点交换其左右孩子,再把孩子入队,效果完全相同。

复杂度

指标	复杂度	原因
时间	O(n)	每个节点被交换一次
空间	O(h)	递归栈深度等于树高

可以迁移的模式

• 「对整棵结构做某种变换」常能归约成「对根做一步局部操作 + 对子结构递归同样的操作」；
• 交换两个引用用元组赋值最干净，省掉临时变量；
• 判断递归顺序是否要紧，只需看这一步会不会破坏后续递归依赖的结构。

能就地改结构的树问题，通常比「重建一棵新树」写得更短。