算法思路
Source
Edit
History

undefined

深度优先算法

1
2
3
4
5
6
7
8
9
10
11
def dfs(node):
    if node in visited:
        # already visited
        return 

    visited.add(node)

    # process current node
    # ... # logic here
    dfs(node.left)
    dfs(node.right) 
1
2
3
4
5
6
7
8
9
visited = set()

def dfs(node, visited):
    visited.add(node)
    # process current node here
    ...
    for next_node in node.children():
        if not next_node in visited:
            dfs(next node, visited)

非递归的写法
模拟了一个栈作为递归的栈 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def DFS(self, tree):
    if tree.root is None:
        return []
    visited, stack = [], [tree.root]

    while stack:
        node = stack.pop()
        visited.add(node)

        process (node)
        nodes = generate_related_nodes(node)
        stack.push(nodes)

    # other processing work
    ...

广度优先遍历

使用队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def BFS(graph, start, end):
    queue = []
    queue.append([start])
    visited.add(start)

    while queue:
        node = queue.pop()
        visited.add(node)

        process(node)
        nodes = genate_related_nodes(node)
        queue.push(nodes)

    # other processing work
    ...

leetcode 433 200