Рекурсивно получить путь к узлу в двоичном дереве

Question

У меня возникают проблемы с получением пути к узлу в двоичном дереве. В частности, я не знаю, как вырезать элементы из стека, когда я возвращаюсь из фрейма стека.

def getPath(self, target): 

    stack = [] 

    def _getPath(head): 
     nonlocal stack 
     nonlocal target 

     stack.append(head) 

     if head.value == target: 
      return stack 
     if head.left is not None: 
      _getPath(head.left) 
     if head.right is not None: 
      _getPath(head.right) 

    _getPath(self.root) 

    return stack 

В настоящее время стек будет содержать все элементы в дереве.

Answer 1

Проблема в том, что информация о том, когда цель найдена, должна быть передана обратно вызываемым экземплярам getPath. Построение стека является своего рода «побочным эффектом» находки. Поэтому я предлагаю вам вернуть логическое значение в getPath, то есть True, если цель была найдена в рамках текущего поддерева. Затем мы знаем, что мы должны приложить значение к «стопке»:

def getPath(self, target): 

    stack = [] 

    def _getPath(head): 
     nonlocal stack 
     nonlocal target 
     if head.value == target: 
      stack.append(head) 
      return True 
     for child in (head.left, head.right): 
      if child is not None: 
       if _getPath(child): 
        stack.append(head) 
        return True 
     return False 


    _getPath(self.root) 
    return reversed(stack)