Day23 - 226. 翻转二叉树

题目链接：https://leetcode.cn/problems/invert-binary-tree/description/

1.问题理解

题目要求翻转一棵二叉树，即将每个节点的左子树和右子树交换位置。
简单理解：把树的每个节点的左右孩子都交换一下。

2.核心算法：递归+前序遍历，后序遍历也可以

• 如果当前节点为空，直接返回 None（递归终止条件）。

• 交换当前节点的左右子树。

• 对左右子树递归调用同样的操作。

• 返回当前节点。

3.关键点和边界条件

1.关键点

交换左右子树的操作要在每个节点上执行一次

递归函数最终必须返回当前节点，这样才能正确连接整棵树。

2.边界条件

root为空，直接返回None

只有一个节点的树，翻转后还是自己

from collections import deque
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        
        queue = collections.deque([root]) #首先加入根节点
        result = []
        while queue:
            level = []
            for _ in range(len(queue)):
                cur = queue.popleft() #队头弹出
                level.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            result.append(level)
        return result