#python #data-structures #binary-tree
#python #структуры данных #двоичное дерево
Вопрос:
Я хочу проверить, равна ли сумма значений в любом пути от начального узла до
существует конечный узел.
Например, предположим, что у меня есть startNode, скажем, 7, а sumTarget равно 15, если дерево:
a-7
b - 1 e- 8
c - 2
d -9
Тогда, поскольку 7 8 равно 15, оно вернет true
Если у меня есть b в качестве startNode и 12 в качестве SumTotal, то он также вернет true, потому что 1 2 9 является 12, начинающимся с b.
class Node {
int value;
Node [] children
}
Я не думаю, что это правильно, но я не уверен, что не так.
def doesSumExist(startNode, sumTarget, currentSum):
totalSum = sumTarget
if startNode is not Null:
if totalSum startNode.value == sumTarget:
return True
else:
totalSum = startNode.value
else:
Node startNode = doesSumExist(startNode.left, sumTarget, currentSum)
if startNode is not Null:
return currentSum
startNode = doesSumExist(startNode.right, sumTarget,currentSum)
return False
Комментарии:
1. Что такое startNode.left и startNode.right? дочерние элементы? Вы не проверяете возвращаемое значение вашего рекурсивного вызова. Вам нужно передать аргумент currentSum вместо того, чтобы каждый раз удалять sumTarget . Вы не хотите проверять, является ли totalSum == startNode.value . Вы хотите проверить, является ли totalSum startNode.value == sumTarget . Вы не хотите назначать totalSum = sumTarget . Вы хотите передать аргумент (как я уже говорил ранее) с именем currentSum . Вам нужно 3 аргумента для этой рекурсивной функции. Если вы объясните мне структуру, которую вы используете, я смогу вам лучше помочь.
2. Да, startNode.left и startNode.right являются дочерними элементами. Я отредактировал сообщение, включив в него образец дерева и чисел, а также изменил код в соответствии с вашими предложениями. Спасибо за вашу помощь. Должно ли в else: totalSum = startNode.value быть вместо totalSum = startNode.left или startNode.right?
Ответ №1:
В этом случае я думаю, что вы ищете что-то вроде следующего:
def doesSumExist(startNode, sumTarget, currentSum):
totalSum = currentSum
if startNode is not Null:
if totalSum startNode.value == sumTarget: #If this node completes the sum
return True
else: #if not
totalSum = startNode.value #increase current sum
if doesSumExist(startNode.left, sumTarget, totalSum): #recursive starting on the left children
return True
elif doesSumExist(startNode.right, sumTarget, totalSum): #recursive starting on the right children
return True
return False #if the sum is not present (starting in startNode).
Однако это не проверяет, содержит ли какая-либо последовательная комбинация узлов сумму (код будет намного сложнее).
Надеюсь, это поможет
Комментарии:
1. Спасибо. Да, я действительно пытаюсь выяснить, содержит ли сумму не только, скажем, два узла, но и три узла или более, как вы сказали. Я буду работать над этим больше самостоятельно, чтобы заставить его работать. Спасибо за вашу помощь!
2. Код, который я разместил, будет работать для любого заданного числа последовательных узлов. Однако, если у вас есть сумма внутри дерева, но она не существует, если вы запускаете в startNode , он ее не найдет. Представьте свое дерево, если вы делаете doesSumExist(a, 12, 0), оно не найдет его, потому что сумма начинается с b, а не с a . Понимаете?
3. В случае, когда она начинается с b, это будет (b, 12, 0), я собираюсь изменить код, чтобы заставить этот случай работать также. Но для этого мне может потребоваться несколько попыток. Но я отправлю ответ, как только доберусь дальше. Еще раз спасибо!
4. Если он начинается с b, он также найдет его, я думаю, что я неправильно объясняю себя. Он находит любую существующую сумму в пути, учитывая, что она всегда будет начинаться в startNode (независимо от узла, который вы передаете функции). Однако, если сумма существует в дереве, но она начинается дальше, она не будет проверена. В вашем примере дерево содержит сумму 12, если вы начинаете с b. Но если вы вызовете функцию doesSumExist(a, 12, 0), она скажет, что это не так, потому что она будет содержать значение 9 из a .
Ответ №2:
предполагая, что ваш класс узла выглядит примерно так:
class Node:
def __init__(self, value = 0, children = None):
self.value = value
self.children = [] if children is None else children
тогда этот метод должен сделать свое дело:
def doesSumExist(startNode, targetSum, currentSum):
if startNode is None:
return False
currentSum = startNode.value
if currentSum == targetSum:
return True
for child in startNode.children:
if doesSumExist(child, targetSum, currentSum):
return True
return False
Обратите внимание, что для этого дизайна класса узла проверка отсутствия startNode на самом деле не требуется для рекурсии, а только для точки входа. Так что, вероятно, это было бы лучше:
def doesSumExist(startNode, targetSum):
def inner(node, targetSum, currentSum):
currentSum = node.value
if currentSum == targetSum:
return True
#for people who like to save a few lines
#return any(inner(child, targetSum, currentSum) for child in node.children)
for child in node.children:
if inner(child, targetSum, currentSum):
return True
return False
if startNode is None:
return False
return inner(startNode, targetSum, 0)
Редактировать:
Если вы не только хотите знать, существует ли сумма в пути от вашего начального узла, но и будет ли она существовать в любом заданном подпути, это должно сработать:
def doesSumExist(startNode, targetSum):
def inner(node, targetSum, allValues):
allValues.append(node.value)
currentSum = 0
for val in reversed(allValues):
currentSum = val
if currentSum == targetSum:
return True
for child in node.children:
if inner(child, targetSum, allValues):
return True
allValues.pop()
return False
if startNode is None:
return False
return inner(startNode, targetSum, [])
Комментарии:
1. Спасибо. Я попробую это!
2. добро пожаловать, надеюсь, это поможет. Однако это также не будет работать для нахождения сумм в подпутях, как указано ниже. Я отредактировал свой пост с другой версией, которая также должна работать для этого.