树的深度优先遍历python

以下是树的深度优先遍历的Python代码示例：

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, depth: int) -> int:
        if not node:
            return depth
        left_depth = self.dfs.left, depth + 1)
        right_depth = self.dfs(node.right, depth + 1)
        return max(left_depth, right_depth)
    
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return self.dfs(root, 0)

其中，`TreeNode`类表示树的节点，`Solution`类中的`dfs`方法是递归实现的深度优先遍历，`maxDepth`方法是调用`dfs`方法并返回最大深度。

相关问题

图的深度优先遍历python

以下是Python中图的深度优先遍历的实现方法：

# 定义一个图类
class Graph:
    def __init__(self, graph_dict=None):
        if graph_dict is None:
            graph_dict = {}
        self.__graph_dict = graph_dict

    # 添加节点
    def add_node(self, node):
        if node not in self.__graph_dict:
            self.__graph_dict[node] = []

    # 添加边
    def add_edge(self, edge):
        edge = set(edge)
        (node1, node2) = tuple(edge)
        if node1 in self.__graph_dict:
            self.__graph_dict[node1].append(node2)
        else:
            self.__graph_dict[node1] = [node2]

    # 深度优先遍历
    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
        print(start)
        for next_node in self.__graph_dict[start]:
            if next_node not in visited:
                self.dfs(next_node, visited)

# 创建一个图实例
graph = Graph()

# 添加节点
graph.add_node('A')
graph.add_node('B')
graph.add_node('C')
graph.add_node('D')
graph.add_node('E')

# 添加边
graph.add_edge(('A', 'B'))
graph.add_edge(('B', 'C'))
graph.add_edge(('C', 'D'))
graph.add_edge(('D', 'E'))
graph.add_edge(('E', 'A'))

# 深度优先遍历
graph.dfs('A')

输出结果为：

A
B
C
D
E

有向图的深度优先遍历python

有向图的深度优先遍历（Depth First Search, DFS）是一种用于遍历图的算法。它从图中的一个顶点开始，沿着一条路径尽可能深地访问图中的顶点，直到无法继续前进为止，然后回溯到前一个顶点，继续探索其他路径。以下是一个用Python实现有向图深度优先遍历的示例代码：

# 定义有向图类
class DirectedGraph:
    def __init__(self):
        self.graph = {}

    # 添加边
    def add_edge(self, start, end):
        if start in self.graph:
            self.graph[start].append(end)
        else:
            self.graph[start] = [end]

    # 深度优先遍历
    def dfs(self, start):
        visited = set()  # 记录已访问的节点

        def dfs_helper(node):
            visited.add(node)
            print(node, end=" ")  # 输出节点值

            if node in self.graph:
                for neighbor in self.graph[node]:
                    if neighbor not in visited:
                        dfs_helper(neighbor)

        dfs_helper(start)

# 创建有向图对象
graph = DirectedGraph()

# 添加边
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('B', 'E')
graph.add_edge('C', 'F')

# 深度优先遍历
print("深度优先遍历结果：")
graph.dfs('A')

运行以上代码，输出结果为：A B D E C F