Python中递归调用的冒泡返回值

Question

我不熟悉如何在Python中从递归函数调用中弹出一个返回调用。在这个例子中，我写了一个“check if something is a binary tree method”，它必须返回true或false。但是，如果我从另一个函数调用它（即使在我遇到条件时），我不会得到False返回。在

我怎样才能确保回电一直持续下去？在

def isValidTree(root, tempArr):
    if(root.left):
        return isValidTree(root.left, tempArr)

    if(len(tempArr) == 0):
        tempArr.append(root.data)
    elif(tempArr[len(tempArr) - 1] >= root.data):
        return False
    else:
        tempArr.append(root.data)

    if(root.right):
        return isValidTree(root.right, tempArr)

def isBinarySearchTree(root):
    print(isValidTree(root, []))

Answer 1

与其只返回对isValidTree(root.left)和isValidTree(root.right)的递归调用的结果，不如检查递归调用是否返回False，在这种情况下，将False结果传播给调用者。此外，如果没有遇到错误，则应返回True：

def isValidTree(root, tempArr):
    if root.left:
        if not isValidTree(root.left, tempArr):
            # Propagate error in left subtree to the parent.
            return False

    if len(tempArr) == 0:
        tempArr.append(root.data)
    elif tempArr[len(tempArr) - 1] >= root.data:
        return False
    else:
        tempArr.append(root.data)

    if root.right:
        if not isValidTree(root.right, tempArr):
            # Propagate error in right subtree to the parent.
            return False

    # No errors encountered, so it was valid.
    return True

Answer 2

当您遍历树时，代码的结构方式没有完成，应该返回的值True或{}来指示子树的有效性。正如@Vasif所指出的，您返回的不是您想要的string或{}。在

你需要先测试一下基本条件，那就是我在叶子上吗？

我不知道你在用坦帕做什么，但我会把它留在里面。在

def is_bst_tree(treenode, temp_arr):
    if treenode.isempty():  # this should be a method on your treenode data type
        return True

    # do the check of the curent value 
    # based on being on the left or right 
    # side of tree   

    # return False # this should be done after you have made the relevant checks


    return is_bst_tree(treenode.right,temp_arr) and is_bst_tree(treenode.left, temp_arr)

“冒泡”将发生在函数末尾的递归调用中，这是基于检查或您位于叶的事实。 您将得到一个boolean and ... and boolean的链，它将解析为True或{}。在

您可以根据https://en.wikipedia.org/wiki/Binary_search_tree#Verification调整算法 有关最小值和最大值，请参见Maximum and Minimum values for ints