226. 翻转二叉树

🎯 问题描述（来源于LeetCode）

描述：给定一个二叉树的根节点 root，请翻转这棵树，即交换每个节点的左子树和右子树，并返回翻转后的根节点。

说明：

这是一个经典的树形操作问题，核心在于理解“镜像”概念。

示例：

示例 1：

1
2
3

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
解释：根节点4的左右孩子2和7互换，随后2的左右孩子1和3互换，7的左右孩子6和9互换。

💻 解题思路

思路1：递归 (自底向上)

核心思想：
利用二叉树的分治思想。翻转一棵树 = 翻转左子树 + 翻转右子树 + 交换左右指针。

基准情况：如果当前节点为空，直接返回空。
递归拆解：假设 invertTree 函数已经帮我们把左右子树翻好了。
合并结果：将翻好的右子树挂在左边，翻好的左子树挂在右边。

思路1：代码实现

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 1. 基准情况 (Base Case)
        if not root:
            return None
        
        # 2. 递归拆解：获取已经翻转好的左右子树
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        
        # 3. 核心操作：交换
        root.left, root.right = right, left
        
        return root

思路1：📊 性能分析

提交结果
- 运行时间：0ms击败100.00%
- 内存消耗：19.17MB击败32.55%
复杂度验证
- 时间复杂度： $O(N)$ $O (N)$
  - 解析：必须访问树中的每一个节点恰好一次。
- 空间复杂度： $O(H)$ $O (H)$
  - 解析：递归调用栈的深度。 $H$ 为树的高度。最坏情况下（退化为链表）为 $O(N)$ ，平均情况下为 $O(\log N)$ 。

思考

递归的本质：
这段代码展示了递归的精髓——“相信函数”。在写 left = self.invertTree(...) 时，不要去想它内部怎么执行的，只要相信它执行完后，左子树已经翻转好了。
前序 vs 后序：
- 上述代码是后序遍历（先处理孩子，再处理父亲）。
- 也可以用前序遍历（先交换当前节点的左右孩子，再递归处理子节点）。
- 两者的时间复杂度一致，但后序写法在逻辑上更符合“分治”的直觉。
迭代解法：
递归本质上是系统栈的调用。我们也可以用显式的栈（Stack）或者队列（Queue）来模拟这个过程（BFS 或 DFS 迭代版）。