python - 使用 DFS 计算树的深度

Question

我正在尝试使用Python编写代码，使用DFS而不是BFS返回树中最深叶子的深度，每个节点有任意数量的子节点。看起来我已经很接近了，但是下面的代码仍然有一些我无法弄清楚的错误(即返回的深度不正确)。有什么帮助吗？

测试树很简单:[[1,2,3],[4,5],[6],[7],[8],[],[],[],[]]

def max_depth_dfs(tree): # DOESN'T WORK

    max_depth, curr_depth, Q = 0,0, [0]
    visited = set()

    while Q != []:
        n = Q[0]
        more = [v for v in tree[n] if v not in visited]
        if not more:
            visited.add(n)
            curr_depth -= 1
            Q = Q[1:]
        else:
            curr_depth += 1

        max_depth = max(max_depth, curr_depth)
        Q = more + Q

    return max_depth

Answer 1

我发现了这个错误!

if not more:
    visited.add(n)
    curr_depth -= 1
    Q = Q[1:]

当您访问节点 4 时，curr_深度等于 2。节点 4 没有子节点，因此您减小了 curr_深度，现在 curr_depth 等于 1。但是，您将访问的下一个节点是节点 5，而节点 5 的深度是 2，而不是 1。因此，curr_depth 不会记录树中节点的正确深度。

以下解决方案可能会有所帮助。

def max_depth_dfs(tree):

    max_depth, curr_depth, Q = 0, 0, [0]
    visited = set()

    while Q != []:
        n = Q[0]

        max_depth = max(max_depth, curr_depth)

        if n in visited:
            curr_depth -= 1
            Q = Q[1:]
            continue

        #print n, curr_depth     #show the node and its depth in the tree

        visited.add(n)
        more = [v for v in tree[n]]
        if not more:
            Q = Q[1:]
        else:
            curr_depth += 1
            Q = more + Q

    return max_depth