從Python中的遞歸調用鼓起返回值

我不熟悉如何從Python中的遞歸函數調用中喚起返回調用。在這個例子中，我正在寫'檢查是否是二叉樹方法'，它必須返回true或false。但是，如果我從另一個函數調用它（即使我打我的條件），我不會得到False返回。從Python中的遞歸調用鼓起返回值

我怎樣才能確保這個回訪電話一路順利？

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, []))

來源

2017-05-25 Xelad1

A部分：在您若情況下，你是返回在兩種情況下無（儘管隱含的）。 B部分：你想要這個tempArr做什麼。如果這恰好是一個二進制數組獲取所有的葉值？ – Vasif

另外，您正在返回'False'作爲字符串。這是一個真正的價值。嘗試將False作爲關鍵字返回。 – Vasif

@Vasif我應該爲此明確地返回一些東西在我的情況下？臨時數組添加樹的每個葉子（通過遍歷），然後檢查數組中的前一個值是否按正確的順序排列。即一個值1,2,3,4,5的BST應該是這樣的順序。 – Xelad1

而不是隻返回遞歸調用isValidTree(root.left)和isValidTree(root.right)的結果，你應該檢查是否遞歸調用返回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

來源

2017-05-26 00:41:03

當你遍歷樹應返回，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 算法對於最小值和最大值看到Maximum and Minimum values for ints

來源

2017-05-26 00:59:10

從Python中的遞歸調用鼓起返回值

回答

相關問題