第66天：Python 反转二叉树，递归镜像交换实现完美树对称（LeetCode #226 风格）

Source: Dev.to

欢迎来到 #80DaysOfChallenges 之旅的第 66 天！本次中等难度挑战聚焦于 通过递归交换左右子节点来翻转二叉树，将结构转换为镜像同时保持节点值不变。它使用递归遍历来翻转子树，是对称性检查、平衡等树操作的基础技巧。如果你正从基础递归迈向树算法，或在为面试（LeetCode #226）做准备，这段 “Python invert binary tree” 脚本展示了一个优雅、就地（in‑place）且易于改写为迭代版本的函数。

💡 第 66 天关键要点：树翻转函数

1. 函数设计：递归交换与基准情况

def invert_tree(tree: dict, node):
    """Recursively invert the binary tree starting from the given node."""
    if node is None:
        return

    left, right = tree.get(node, (None, None))   # get left and right children
    tree[node] = (right, left)                   # swap children

    invert_tree(tree, left)   # invert left subtree
    invert_tree(tree, right)  # invert right subtree

• 基准情况在 node 为 None 时返回。
• 使用 dict.get 获取子节点，默认返回 (None, None)。
• 交换元组后，函数递归处理左右子树。
• 复杂度： O(n) 时间，O(h) 空间（h 为树高）。

2. 树结构：基于字典的表示

tree = {
    "A": ("B", "C"),
    "B": ("D", "E"),
    "C": (None, "F"),
    "D": (None, None),
    "E": (None, None),
    "F": (None, None),
}

• 键为节点标识；值为 (left_child, right_child) 元组。
• 对于不需要自定义节点类的小树来说，简单且方便。

3. 主示例：翻转前后对比

root = "A"                    # root of the tree

print("Original tree:")
print(tree)

invert_tree(tree, root)       # invert the tree in‑place

print("\nInverted tree:")
print(tree)

• 输出显示根节点的子节点已交换（A 变为 ("C", "B")），同样的转换递归应用到所有子树。

🎯 总结与思考

• 递归模式： 基准情况 → 处理（交换） → 递归子节点。
• 字典存树： 当不需要基于类的节点时，灵活的表示方式。
• 就地修改： 避免额外的内存分配。

可以进一步扩展为使用栈或队列的迭代版本，或通过比较原始结构与翻转后结构来检查树的对称性。

🚀 后续步骤与资源

• 挑战 #66 的源码： scripts/invert_binary_tree.py
• 主仓库： 80-days-of-challenges
• 每日更新： Twitter/X (@Shahrouzlogs)