DFS 递归写法
visited = set()
def dfs(node, visited):
# 1. terminator
if node in visited:
return
visited.add(node)
# process_current_logic
...
for next_node in node.children():
if not next_node in visited:
dfs(next_node, visited)
DFS 非递归写法
def dfs(self, root):
if not root:
return
visited, stack = [], [root]
while stack:
node = stack.pop()
visited.add(node)
process(node)
nodes = generate_related_nodes(node)
stack.push(nodes)
# other processing work
BFS 代码
def bfs(self, root):
if not root:
return
visited, queue = [], [root]
while queue:
node = queue.pop()
visited.add(node)
process(node)
nodes = generate_related_nodes(node)
queue.push(nodes)
Java DFS 层序遍历
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> allResults = new ArrayList<>();
if (root == null) {
return allResults;
}
travel(root, 0, allResults);
return allResults;
}
private void travel(TreeNode root, int level, List<List<Integer>> results) {
if (results.size() == level) {
results.add(new ArrayList<>());
}
results.get(level).add(root.val);
if (root.left != null) {
travel(root.left, level + 1, results);
}
if (root.right != null) {
travel(root.right, level + 1, results);
}
}
其它资料
AlphaZero Explained
棋类复杂度