实现二叉树的遍历（前序、中序、后序、层次遍历任选其一）python

在Python中，我们可以使用递归或栈来实现二叉树的遍历。这里我将展示如何使用递归实现三种常见的二叉树遍历：前序遍历、中序遍历和后序遍历。

1. **前序遍历** (根-左-右)：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder_traversal(root):
    if root is not None:
        print(root.val)
        preorder_traversal(root.left)
        preorder_traversal(root.right)

2. **中序遍历** (左-根-右)：

def inorder_traversal(root):
    if root is not None:
        inorder_traversal(root.left)
        print(root.val)
        inorder_traversal(root.right)

3. **后序遍历** (左-右-根)：

def postorder_traversal(root):
    if root is not None:
        postorder_traversal(root.left)
        postorder_traversal(root.right)
        print(root.val)

4. **层次遍历** (广度优先搜索，从上到下逐层遍历) 使用队列辅助：

from collections import deque

def level_order_traversal(root):
    if root is None:
        return []
    queue = deque([root])
    result = []
    while queue:
        level_size = len(queue)
        current_level = [node.val for node in queue]
        result.append(current_level)
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return result