Определение глубины в поиске глубины

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