尝试理解python中二叉树(递归函数)中存在的节点

Question

我正在尝试理解下面的递归函数，它表示一个特定的节点是否存在于二叉树中。我做了一些准备工作，得到了大部分递归部分，但最后一条返回语句( root.value、==、value或inleft或inright)让我感到困扰。

有没有人能帮我理解一下这个方法？

    def existsInTree(self, root, value):
        if root is None:
            return False
        else:
            inleft = self.existsInTree(root.left, value)
            inright = self.existsInTree(root.right, value)
            print(inleft,inright)
            return root.value == value or inleft or inright

 example binary tree:

            10
           /  \
        11     9

Answer 1

我们首先将根的数据与要搜索的节点的数据进行比较。如果找到匹配项，则将该标志设置为true。否则，在左子树中搜索节点，然后在右子树中搜索节点。

Answer 2

还有另一种查看返回语句的方法，您可以在or关键字处拆分返回语句

def ifRootExists(self,root, value):
 
    if (root == None):
        return False
 
    if (root.value == value):
        return True
 
    """ then recur on left sutree """
    res1 = ifrootExists(root.left, value)
    # root found, no need to look further
    if res1:
        return True
 
    """ root is not found in left,
    so recur on right subtree """
    res2 = ifrootExists(root.right, value)
 
    return res2

Answer 3

我们可以从上面的函数中得到某个节点是否存在的结果。

算法如下。

1. 根目录为None或不是。如果无，则返回父函数使用"False".
2. Otherwise，值调用的位置基于当前node.

• inleft连续搜索的函数是"existsInTree“函数的值，其中当前节点的左子节点是根节点。
• inright是函数"existsInTree”的值，其中当前节点的右子节点是根节点。假设我们要搜索值，称为V。如果V存在于树中，则表示当前值是V或在左侧树中，或在右侧树中。

总而言之，inleft和inright表示V是否包含在子树中。