我试图在二叉树分支中找到 nodeA 和 nodeB。我返回的总和应该等于找到的节点数。这是我的实现
def checkSubtree(self, nodeA, nodeB, node):
if node is None:
return 0
if node is nodeA or node is nodeB:
return 1
return self.checkSubtree(nodeA, nodeB, node.leftChild) + self.checkSubtree(nodeA, nodeB, node.rightChild)
当我应该得到 2 时，我一直得到 1。我发现这是因为第二个 if 语句在第一次传递时执行并立即返回。
我该如何改进。我不想使用额外的变量来存储结果并返回它。
最佳答案
nodeA 或 nodeB 节点仍然可以有子节点，它们可能是 nodeA 或 nodeB 节点。
使用return 1，您一遇到nodeA 或nodeB 节点就停止了递归搜索。
一个解决方案是:
def checkSubtree(self, nodeA, nodeB, node):
if node is None:
return 0
else:
children_sum = self.checkSubtree(nodeA, nodeB, node.leftChild) + self.checkSubtree(nodeA, nodeB, node.rightChild)
if node is nodeA or node is nodeB:
return 1 + children_sum # <-- Important. Not just 1 !
else:
return children_sum
如果出于某种原因你现在想要定义一个局部变量:
def checkSubtree(self, nodeA, nodeB, node):
if node is None:
return 0
else:
return self.checkSubtree(nodeA, nodeB, node.leftChild) + self.checkSubtree(
nodeA, nodeB, node.rightChild) + int(node is nodeA or node is nodeB)
关于python - 试图在二叉树中查找节点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45080113/