在Python中，如何用递归与迭代方式分别实现二叉树的深度优先搜索（DFS）和广度优先搜索（BFS）？并请解释每种方法在遍历二叉树时的工作原理。

在处理数据结构时，二叉树是极其重要的概念，其遍历是基础且核心的问题。在Python中，二叉树遍历可以通过深度优先搜索（DFS）和广度优先搜索（BFS）两种方式进行。深度优先搜索利用递归易于实现，而广度优先搜索则常使用迭代和队列来完成。以下是如何使用递归实现DFS和迭代实现BFS的详细解释和代码示例：

参考资源链接：[Python遍历二叉树：递归DFS与迭代BFS实现](https://wenku.csdn.net/doc/32rwi50kno?spm=1055.2569.3001.10343)

深度优先搜索（DFS）利用了递归的调用栈特性，通过递归函数访问树中的每一个节点。具体来说，它先访问根节点，然后递归地访问左子树，接着递归地访问右子树。在Python中，可以使用递归函数来实现前序、中序和后序遍历。前序遍历（根-左-右）的递归代码示例如下：

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

def dfs(node):
    if node:
        print(node.val)  # 访问节点值
        dfs(node.left)   # 递归遍历左子树
        dfs(node.right)  # 递归遍历右子树

# 示例二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 调用dfs函数进行前序遍历
dfs(root)

广度优先搜索（BFS）使用队列来追踪待访问的节点，按照层次的顺序访问节点。BFS从根节点开始，先访问根节点的所有直接子节点，然后是子节点的子节点，依此类推。在Python中，可以使用队列数据结构（如`collections.deque`）来实现BFS。BFS的迭代代码示例如下：

from collections import deque

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

def bfs(node):
    if not node:
        return
    queue = deque([node])  # 初始化队列，根节点入队
    while queue:
        current_node = queue.popleft()  # 访问队首节点
        print(current_node.val)  # 输出节点值
        if current_node.left:
            queue.append(current_node.left)  # 左子节点入队
        if current_node.right:
            queue.append(current_node.right)  # 右子节点入队

# 示例二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 调用bfs函数进行广度优先遍历
bfs(root)

理解递归和迭代的不同遍历方式对于深入学习二叉树非常重要。递归方法简洁，但要注意避免栈溢出，尤其在处理大型树时。而迭代方法虽然需要额外处理队列，但更加灵活且易于理解层次遍历的原理。每种方法都适合不同的应用场景，递归常用于需要回溯的场景，如路径搜索问题，而迭代则更适合最短路径问题，如层级遍历。通过这两段代码，你可以掌握二叉树遍历的两种基本方法，以及如何将递归和迭代应用于实际问题解决中。

参考资源链接：[Python遍历二叉树：递归DFS与迭代BFS实现](https://wenku.csdn.net/doc/32rwi50kno?spm=1055.2569.3001.10343)