LeetCode 深度优先搜索（DFS）题解

LeetCode 深度优先搜索（DFS）题解

题目描述

深度优先搜索是一种用于遍历或搜索树或图的算法。该算法从根节点开始，沿着一条路径尽可能深地探索，直到不能继续为止，然后回溯到上一个节点，继续探索其他路径。

示例：

对于以下树结构：

1 / \ 2 3 / \ 4 5

深度优先搜索的遍历顺序可以是：1 → 2 → 4 → 5 → 3。

解题思路

方法：深度优先搜索

思路：

• 深度优先搜索的核心思想是尽可能深地探索图或树的路径，直到不能继续为止，然后回溯。
• 对于树结构，深度优先搜索可以分为前序遍历、中序遍历和后序遍历。
• 对于图结构，深度优先搜索需要记录已访问的节点，以避免重复访问。

复杂度分析：

• 时间复杂度：O(V + E)，其中 V 是顶点数，E 是边数。每个顶点和边都会被访问一次。
• 空间复杂度：O(V)，需要使用栈来存储递归调用的信息，最坏情况下栈的深度为 V。

代码实现

方法：深度优先搜索（树的前序遍历）

# 定义树节点 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 = [] stack = [root] while stack: node = stack.pop() result.append(node.val) # 先压入右子节点，再压入左子节点，这样弹出时会先处理左子节点 if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result # 测试 def test_dfs_preorder(): # 构建树结构 root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) # 测试前序遍历 print(dfs_preorder(root)) # 输出：[1, 2, 4, 5, 3] if __name__ == "__main__": test_dfs_preorder()

方法：深度优先搜索（图的遍历）

# 深度优先搜索（图的遍历） def dfs_graph(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start, end=' ') for neighbor in graph[start]: if neighbor not in visited: dfs_graph(graph, neighbor, visited) # 测试 def test_dfs_graph(): # 构建图结构 graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } # 测试图的遍历 print("DFS traversal starting from A:") dfs_graph(graph, 'A') # 输出：A B D E F C if __name__ == "__main__": test_dfs_graph()

测试用例

测试用例 1：树的前序遍历

输入：

1 / \ 2 3 / \ 4 5

输出：[1, 2, 4, 5, 3]

测试用例 2：图的遍历

输入：

A -- B -- D | | C -- F -- E

输出：A B D E F C

总结

深度优先搜索是一种重要的图论算法，它可以用于遍历树和图，以及解决许多相关问题，如路径查找、连通性判断等。通过递归或栈的方式，深度优先搜索可以高效地探索图或树的结构。

深度优先搜索的核心思想是：尽可能深地探索路径，直到不能继续为止，然后回溯到上一个节点，继续探索其他路径。

掌握深度优先搜索的原理和实现，对于理解和解决图论相关问题非常重要。