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

Question

我不熟悉如何在 Python 中从递归函数调用中冒出返回调用。在这个例子中，我正在编写一个"检查某物是否是二叉树方法"，它必须返回 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或False来指示子树的有效性(未完成。如@Vasif所示，您退回的string或None不是您想要的。

您需要先测试基本条件，即我在叶子吗？

我不确定你在用 tempArr 做什么，但我会把它留在里面。

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或False。

您可以从 https://en.wikipedia.org/wiki/Binary_search_tree#Verification 调整算法有关最小值和最大值，请参阅整数的最大值和最小值