dfs如何使用的列子

深度优先搜索（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(root):
    if root is None:
        return []

    visited = [root]
    result = []

    while visited:
        current_node = visited.pop(0)  # 选择第一个节点并移除已访问列表
        result.append(current_node.val)  # 将当前节点值添加到结果

        # 添加当前节点的未访问子节点
        if current_node.left:
            visited.append(current_node.left)
        if current_node.right:
            visited.append(current_node.right)

    return result

# 示例
#     1
#    / \
#   2   3
#  / \   \
# 4   5   6
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6)))
print(dfs(root))  # 输出: [1, 2, 4, 5, 3, 6]

在这个例子中，`dfs`函数首先检查根节点是否为空，然后创建一个队列`visited`存储待访问的节点。当`visited`非空时，它会取出第一个节点，访问其值，然后将它的子节点加入`visited`。这个过程一直持续到所有节点都被访问过。