🔗 翻转二叉树

题目来源：226. 翻转二叉树 – 力扣（LeetCode）

📌 题目描述

给你一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。

翻转的意思是：对于每个节点，交换它的左子树和右子树。

✅ 示例解析

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
解释：每个节点的左右子节点都被交换，例如 2 和 7 互换，1 和 3 与 6 和 9 也分别互换。

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]
解释：根节点 2 的左右子节点 1 和 3 被交换。

示例 3：

输入：root = []
输出：[]
解释：空树翻转后仍为空树。

⚠️ 提示

• 树中节点数目范围在 [0, 100] 内
• -100 <= Node.val <= 100

💡 解法：递归（后序遍历）—— O(n) 时间，O(h) 空间

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

📊 复杂度分析

• 时间复杂度：O(n)
  每个节点恰好被访问一次，总共有 n 个节点，因此时间复杂度为 O(n)。
• 空间复杂度：O(h)
  递归调用栈的深度等于树的高度 h。最坏情况下（链状树），h = n；最好情况下（完全平衡树），h = log n。因此空间复杂度为 O(h)。

🧩 解题思路

递归思想：
要翻转一棵二叉树，只需：

1. 递归翻转左子树；
2. 递归翻转右子树；
3. 将当前节点的左、右子树交换。