深度优先搜索确定深度

Question

我正在做一个任务，我要在树中找到一只动物。

在这种情况下，我使用深度优先搜索和递归实现，迄今为止都是很好的。

但是，我必须在这棵树内打印出这个动物的深度。我根本不知道从哪里开始，也没有在网上找到很多有用的材料。

这是类框架。

class Node: 
    children = None 
    ratatosk = None 

    def __init__(self): 
     self.children = [] 
     self.ratatosk = False 

这是我的实现。

def dfs(root): 
    for children in root.children: 
     if root.ratatosk: 
      return True # should return depth 
     dfs(children) 

任何帮助表示赞赏，谢谢。

Answer 1

下面是返回双方的深度和找到的对象版本：

def search(root): 
    if root.ratatosk: 
     return root, 0 
    for i in root.children: 
     found, depth = search(i) 
     if found is not None: 
      return found, depth + 1 
    return None, 0 

class Node: 
    def __init__(self): 
     self.children = [] 
     self.ratatosk = False 

# example 

thing = Node() 
obj = Node() 
layer1 = Node() 
layer2 = Node() 

thing.ratatosk = True 
obj.children.append(layer1) 
layer1.children.append(layer2) 
layer2.children.append(thing) 

found, depth = search(obj) 
print(found, found is thing, depth) # <__main__.Node object at 0x7fc652c5efd0> True 3