实现二叉树的先序遍历、中序遍历和后序遍历的递归算法和层次遍历算法

实现二叉树的遍历有三种基本方式：先序遍历、中序遍历和后序遍历，它们都是通过递归实现的。

1. **先序遍历（Preorder Traversal）**：
- 对根节点执行操作；
- 递归地对左子树进行先序遍历；
- 递归地对右子树进行先序遍历。
递归代码示例：

   def preorder_traversal(root):
       if root is not None:
           print(root.val)  # 先访问根节点
           preorder_traversal(root.left)  # 再遍历左子树
           preorder_traversal(root.right)  # 最后遍历右子树

2. **中序遍历（Inorder Traversal）**：
- 递归地对左子树进行中序遍历；
- 对根节点执行操作；
- 递归地对右子树进行中序遍历。
递归代码示例：

   def inorder_traversal(root):
       if root is not None:
           inorder_traversal(root.left)
           print(root.val)  # 中间访问根节点
           inorder_traversal(root.right)

3. **后序遍历（Postorder Traversal）**：
- 递归地对左子树进行后序遍历；
- 递归地对右子树进行后序遍历；
- 对根节点执行操作。
递归代码示例：

   def postorder_traversal(root):
       if root is not None:
           postorder_traversal(root.left)
           postorder_traversal(root.right)
           print(root.val)  # 最后访问根节点

4. **层次遍历（Level Order Traversal，也叫广度优先遍历）**：
- 使用队列存储待访问节点；
- 将根节点入队；
- 当队列不为空时，依次出队并访问当前节点，然后将左右子节点（如果存在）入队；
- 重复以上步骤直到队列为空。
非递归版本：

   from collections import deque

   def level_order_traversal(root):
       if root is None:
           return
       queue = deque([root])
       while queue:
           node = queue.popleft()
           print(node.val, end=" ")  # 按层打印节点值
           if node.left:
               queue.append(node.left)
           if node.right:
               queue.append(node.right)