深度优先搜索

示例代码
python
class TreeNode:
def init(self, val):
self.val = val;
self.left, self.right = None, None

C++
Struct TreeNode {
int val;
TreeNode * left;
TreeNode * right;
TreeNode(int x) : val(x),left(NULL),right(NULL) {}
}

Java
public class TreeNode {
public int val;
public TreeNode left, right;

public TreeNode(int val) {
    this.val = val;
    this.left = null;
    this.right = null;
}

}

二叉树dsf 示例代码
def dsf(node):
if node in visited:
# already visited
return

visited.add(node)

# process current node
# ... # logic here
dfs(node.left)
dfs(node.right)

多叉树dsf 示例代码
visited = set()
def dfs(node, visited):
# terminator
if node in visited:
# already visited
return

visited.add(node);

# process current node here
# 遍历所有子节点
for next_node in node.children:
    if not next_node in visited:
        dfs(next_node, visited)

DFS非递归写法
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