剑指 Offer 27：二叉树的镜像递归实现

二叉树的镜像

将一棵二叉树镜像翻转，本质上是把每个节点的左右子树互换。对于根节点来说，就是交换它的左孩子和右孩子指针；对于子节点，同样执行这个操作，直到叶子节点。

这种结构天然适合用递归来处理。我们定义一个函数，接收当前节点作为参数。如果节点为空，直接返回；否则，先交换左右子节点，然后分别对新的左子树和右子树递归调用该函数。

下面是具体的 Python 实现，基于 LeetCode 风格的类定义：

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def mirrorTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return root
        
        # 交换左右子节点
        root.left, root.right = root.right, root.left
        
        # 递归处理左右子树
        self.mirrorTree(root.left)
        self.mirrorTree(root.right)
        
        return root

这段代码的时间复杂度是 O(n)，其中 n 是节点总数，因为每个节点只访问一次。空间复杂度取决于递归栈的深度，最坏情况下为 O(n)（退化成链表时），平均情况为 O(log n)。

注意这里使用了 Python 的元组解包语法来交换变量，这比临时变量更简洁。实际调试时，建议打印一下中序遍历结果来验证镜像是否正确。