翻转二叉树

🟢 Easy · 🏷️ 树、递归、DFS · LeetCode#226

📖 题目

翻转一棵二叉树，返回翻转后的根节点。

     4              4
   /   \    →    /   \
  2     7       7     2
 / \   / \     / \   / \
1   3 6   9   9   6 3   1

🆕 新知识

Python 的元组解包能一步完成"先算出新值，再一起赋值"，天然适合"交换"这种操作：

a, b = b, a   # 交换两个变量，不用借助临时变量
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)

右边两个表达式先都算完，再同时赋给左边——不会出现"改了 root.left 之后，root.right 用到的却是改过的值"这种问题。

💡 思路

和求最大深度是同一个递归骨架，区别是这题在"修改"而不是"查询"：交换当前节点的左右子树，再递归翻转新的左右子树。

💻 代码

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

时间复杂度 O(n)，空间复杂度 O(h)，h 是树高。