如何检查中给定路径的和是否存在

Question

如果我要检查任何路径中的值的和

叶节点存在。在

例如，假设startNode是7，sumTarget是15，如果树是：

        a-7
  b - 1    e- 8
  c - 2    
  d -9 

既然7+8等于15，它就会返回真值

如果我有b作为startNode，12作为sumtool，那么它也会返回true，因为1+2+9是以b开头的12

^{pr2}$

我不认为这是对的，但我不确定是什么错了。在

^{3}$

Answer 1

假设节点类如下所示：

class Node:
    def __init__(self, value = 0, children = None):
        self.value = value
        self.children = [] if children is None else children

那么这个方法应该能做到：

^{pr2}$

注意，对于这个节点类的设计，startNode的None检查对于递归来说并不是真正必要的，而是对于入口点。所以这可能会更好：

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, [])

Answer 2

在这种情况下，我认为您要搜索的内容如下：

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).

但是，这不会检查任何连续的节点组合是否包含总和（代码将更加复杂）。在

希望这有帮助