Skip to main content
 首页 » 编程设计

python之试图在二叉树中查找节点

2025年02月15日8qlqwjy

我试图在二叉树分支中找到 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)