<p>假设节点类如下所示:</p>
<pre><code>class Node:
def __init__(self, value = 0, children = None):
self.value = value
self.children = [] if children is None else children
</code></pre>
<p>那么这个方法应该能做到:</p>
^{pr2}$
<p>注意,对于这个节点类的设计,startNode的None检查对于递归来说并不是真正必要的,而是对于入口点。所以这可能会更好:</p>
<pre><code>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)
</code></pre>
<p>编辑:
如果您不仅想知道该和是否存在于起始节点的路径中,而且还想知道它是否会存在于任何给定的子路径中,那么应该可以:</p>
<pre><code>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, [])
</code></pre>