python - 如何覆盖(或传递)递归函数中的参数？

Question

我正在寻找一种方法来覆盖递归函数中的参数。

我正在编写代码来检查它是否是二叉搜索树，下面是我编写的代码。

class Node:
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def isItBST(root, prev_value, curr_value):
    """
    Using in order traversal, we check if every node is sorted because if it's a BST,
    then it should be sorted.
    """
    if root is not None:
        isItBST(root.left, prev_value, curr_value)
        curr_value = root.data
        print root.data, "curr: ",curr_value, "prev_value: ",prev_value
        if (prev_value > curr_value ):
            print "wrong!" # return False
        prev_value = curr_value
        isItBST(root.right, prev_value, curr_value)

# Define a tree
root = Node(4)
root.left = Node(2)
root.right = Node(5)
root.left.left = Node(1)
root.left.right = Node(8) # This node violates the BT rule

if (isItBST(root,-999999,root.data))==False:
    print "Is Not BST"
else:
    print "Is a BST"

输出:

## -- End pasted text --
1 curr:  1 prev_value:  -999999
2 curr:  2 prev_value:  -999999
8 curr:  8 prev_value:  2
4 curr:  4 prev_value:  -999999
5 curr:  5 prev_value:  4
Is a BST <== which is WRONG

如果您运行此代码，它无法检测到，因为根的参数 prev_value 在递归期间没有得到更新。理想情况下，我想在递归期间更新 prev_value 以便它可以打印“错误!”当 Node(8) 违反 BT 规则时。

您的回答不需要特定于此问题。我将不胜感激任何一种在递归中传递参数的一般想法。

Answer 1

问题是您永远不会返回 True 或 False 来指示它是否是 BST。

def isItBST(root, prev_value, curr_value):
    """
    Using in order traversal, we check if every node is sorted because if it's a BST, then it should be sorted.
    """
    if root is not None:
        if not isItBST(root.left, prev_value, curr_value):
            print "wrong!"
            return False
        curr_value = root.data
        print root.data, "curr: ",curr_value, "prev_value: ",prev_value
        if (prev_value > curr_value ):
            print "wrong!"
            return False
        prev_value = curr_value
        return isItBST(root.right, prev_value, curr_value)
    else:
        return True