尝试在二进制文件中查找节点

Question

我试图在二叉树分支中找到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语句在第一次传递时执行并立即返回

我该如何改进这一点。我不想使用额外的变量来存储结果并返回它

Answer 1

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)