python二叉树遍历BFS与DFS

Python中的二叉树遍历可以使用广度优先搜索（BFS）和深度优先搜索（DFS）两种方法。

BFS（广度优先搜索）是一种逐层遍历二叉树的方法。从根节点开始，按照层级顺序依次访问每个节点，先访问左子节点，再访问右子节点。具体实现可以使用队列来辅助实现。以下是BFS的实现方式：

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

def bfs(root):
    if not root:
        return []
    queue = [root]
    result = []
    while queue:
        node = queue.pop(0)
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

DFS（深度优先搜索）是一种先访问根节点，然后递归地访问左子树和右子树的方法。DFS有三种常见的遍历方式：前序遍历、中序遍历和后序遍历。以下是DFS的实现方式：

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

def dfs_preorder(root):
    if not root:
        return []
    result = []
    result.append(root.val)
    result += dfs_preorder(root.left)
    result += dfs_preorder(root.right)
    return result

def dfs_inorder(root):
    if not root:
        return []
    result = []
    result += dfs_inorder(root.left)
    result.append(root.val)
    result += dfs_inorder(root.right)
    return result

def dfs_postorder(root):
    if not root:
        return []
    result = []
    result += dfs_postorder(root.left)
    result += dfs_postorder(root.right)
    result.append(root.val)
    return result