dfs

DFS（Depth First Search，深度优先搜索）是一种搜索算法，用于在树或图等数据结构中遍历所有节点。DFS 从起始节点开始，沿着一条路径一直遍历到底，直到不能再前进为止，然后返回上一个节点，继续遍历其它路径。DFS 可以用递归或栈来实现。

在 DFS 中，我们可以分为两种遍历方式：深度优先遍历（preorder）、后序遍历（postorder）。深度优先遍历从根节点开始，一直遍历到叶子节点，然后返回上一级节点，进行下一轮遍历。后序遍历则是遍历完子节点之后，再遍历父节点。这两种遍历方式都是基于递归实现的。

下面是一个使用递归实现 DFS 的示例代码（以二叉树为例）：

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

class Solution:
    def dfs(self, node: TreeNode):
        if node is None:
            return
        print(node.val)  # 先访问根节点
        self.dfs(node.left)  # 再遍历左子树
        self.dfs(node.right)  # 最后遍历右子树

    def preorderTraversal(self, root: TreeNode) -> List[int]:
        self.result = []
        self.dfs(root)
        return self.result

在上面的代码中，我们定义了一个 TreeNode 类来表示二叉树中的节点，其中包括节点的值、左子节点和右子节点。我们还定义了一个 Solution 类来实现 DFS 遍历，其中 dfs() 方法用于进行深度优先遍历，preorderTraversal() 方法则是用于求解前序遍历的结果。在 dfs() 方法中，我们先访问根节点，然后再递归遍历左子树和右子树，直到遍历完整棵树。在遍历各个节点的过程中，我们可以将节点的值保存到一个列表中，最后返回即可。

当我们需要使用 DFS 遍历一棵树时，只需要创建一个 Solution 对象，然后调用其对应的方法即可。比如，可以使用如下代码来创建一棵二叉树，然后对其进行 DFS 遍历：

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

solution = Solution()
result = solution.preorderTraversal(root)
print(result)  # 输出: [1, 2, 4, 5, 3]

在上面的代码中，我们首先创建了一棵二叉树，然后创建了一个 Solution 对象，最后调用其 preorderTraversal() 方法来进行遍历。遍历完成后，将遍历结果输出即可。