Необходима ясность в рекурсии двоичного дерева ⇐ Python
-
Anonymous
Необходима ясность в рекурсии двоичного дерева
Я пытаюсь решить задачу поиска узлов на расстоянии K. Я опубликую формулировку задачи.
Вам дан корневой узел двоичного дерева, целевое значение узла, содержащегося в дереве, и положительное целое число k. Напишите функцию, которая возвращает значения всех узлов, находящихся на точном расстоянии k от узла с целевым значением. Расстояние между двумя узлами определяется как количество ребер, которые необходимо пройти, чтобы выйти из одного. узел к другому.
Моя логика заключалась в том, чтобы работать шаг за шагом. Сначала я написал функцию для поиска целевого узла. Затем я выделил все родительские узлы и создал словарь для размещения всех родительских узлов. И, наконец, я создал вспомогательную функцию, которая рекурсивно обходила все узлы, пока не достигала значения Нет или k было отрицательным в качестве базового случая. Быстро понял, что иду в бесконечный цикл, потому что иду по трем путям
[*]Родитель [*]Левый ребенок [*]Правильный ребенок.
и я бы продолжал посещать множество узлов взад и вперед, если бы не поддерживал систему безопасности посещений.
Я написал систему посещения, в которой я преждевременно пометил ее как посещенную, иначе говоря, рекурсивная функция вызывается на узле, отмечает посещенный узел, вызывает рекурсию на другом узле. Моя идея заключалась в том, что если узел не может вернуться к тому же узлу, он перестанет переходить в бесконечный цикл. Но бесконечный цикл продолжался. И мне бы хотелось объяснить, почему. Спасибо.
Мой код:
класс БинарноеДерево: def __init__(self, value, left=None, right=None): self.value = значение self.left = левый self.right = правильно Защиту findNodesDistanceK (дерево, цель, k): targetNode = findtargetNode (дерево, цель) nodeToParents = {дерево: нет} nodeToParents = AssignParentnodes (дерево, nodeToParents) #для элемента в nodeToParents: # если nodeToParents[ele]: # print(ele.value, nodeToParents[ele].value) # еще: # print(ele.value, nodeToParents[ele]) бегущийСписок = список() посетил = список() узлы = помощник (targetNode, k, nodeToParents, RunningList, посещенный) toReturn = список() для эле в узлах: если ele.value != цель: toReturn.append(ele.value) если цель в toReturn: toReturn.remove(цель) setreturn = set(toReturn) список возврата (setreturn) def helper(узел, k, родители, RunningList, посещено): если узел равен None или k
Я пытаюсь решить задачу поиска узлов на расстоянии K. Я опубликую формулировку задачи.
Вам дан корневой узел двоичного дерева, целевое значение узла, содержащегося в дереве, и положительное целое число k. Напишите функцию, которая возвращает значения всех узлов, находящихся на точном расстоянии k от узла с целевым значением. Расстояние между двумя узлами определяется как количество ребер, которые необходимо пройти, чтобы выйти из одного. узел к другому.
Моя логика заключалась в том, чтобы работать шаг за шагом. Сначала я написал функцию для поиска целевого узла. Затем я выделил все родительские узлы и создал словарь для размещения всех родительских узлов. И, наконец, я создал вспомогательную функцию, которая рекурсивно обходила все узлы, пока не достигала значения Нет или k было отрицательным в качестве базового случая. Быстро понял, что иду в бесконечный цикл, потому что иду по трем путям
[*]Родитель [*]Левый ребенок [*]Правильный ребенок.
и я бы продолжал посещать множество узлов взад и вперед, если бы не поддерживал систему безопасности посещений.
Я написал систему посещения, в которой я преждевременно пометил ее как посещенную, иначе говоря, рекурсивная функция вызывается на узле, отмечает посещенный узел, вызывает рекурсию на другом узле. Моя идея заключалась в том, что если узел не может вернуться к тому же узлу, он перестанет переходить в бесконечный цикл. Но бесконечный цикл продолжался. И мне бы хотелось объяснить, почему. Спасибо.
Мой код:
класс БинарноеДерево: def __init__(self, value, left=None, right=None): self.value = значение self.left = левый self.right = правильно Защиту findNodesDistanceK (дерево, цель, k): targetNode = findtargetNode (дерево, цель) nodeToParents = {дерево: нет} nodeToParents = AssignParentnodes (дерево, nodeToParents) #для элемента в nodeToParents: # если nodeToParents[ele]: # print(ele.value, nodeToParents[ele].value) # еще: # print(ele.value, nodeToParents[ele]) бегущийСписок = список() посетил = список() узлы = помощник (targetNode, k, nodeToParents, RunningList, посещенный) toReturn = список() для эле в узлах: если ele.value != цель: toReturn.append(ele.value) если цель в toReturn: toReturn.remove(цель) setreturn = set(toReturn) список возврата (setreturn) def helper(узел, k, родители, RunningList, посещено): если узел равен None или k
