如何在递归 python 函数中正确放置 return 值

Question

我正在遍历二叉树中节点的子节点并检查 locked 属性。 Return False 如果任何子锁状态为 False，否则为 True。我似乎找不到在代码中放置 return 语句的正确方法。请注意，lock 函数的输入是一个节点对象。

class BinaryTree():
    def __init__(self, value, lock=False):
        self.locked = lock
        self.value = value
        self.left = None
        self.right = None

    def lock(self, node_object):
        """lock a node if the descendants are locked using post-order traversing"""
        flag = True
        if node_object.left:
            if node_object.left.locked == True:
                print(
                    f'>>> Left child: {node_object.left.value}. Locked?: {node_object.left.locked} <<<')
                self.lock(node_object.left)
            else:
                flag = False
                print(
                    f'>>> Children Node: {node_object.left.value}\tstate: {node_object.left.locked}. Lock failed <<<')
        if node_object.right:
            if node_object.right.locked == True:
                print(
                    f'>>> Right child: {node_object.right.value}. Locked?: {node_object.right.locked} <<<')
                self.lock(node_object.right)
            else:
                flag = False
                print(
                    f'>>> Children Node: {node_object.right.value}\tstate: {node_object.right.locked}. Lock failed <<<')
        return flag

# test the functions
if __name__ == "__main__":
    BT = BinaryTree(None)
    count = 0
    lock_state = False
    nodes = [34, 2, 1, 6, 8, 9, 56, 99, 150, 45, 3]
    for item in nodes:
        BT.add_node(item, lock_state)  # test add_node
    node = BT.find_node(56)  # test find_node function
    if node is not None:
        status = BT.lock(node)
        print(status)

status 始终是 True，即使执行了 else 语句。

Answer 1

为了正确递归，让我们看一下基本情况：

如果当前节点已解锁，returnFalse
如果left存在并解锁，return假
如果right存在并解锁，return假
Return 正确

left 和 right 的检查应该递归完成：

def is_locked(self):
     return self.locked and (not self.left or self.left.is_locked()) and (not self.right or self.right.is_locked())

由于and和or是short-circuiting运算符，所以只检查需要检查的树。请注意，我们使用 children 调用中的 return 值，这与您的原始代码不同。

根据评论，您可以使用 built-in all 概括此方法。虽然对于二叉树不是特别有用，但这种方法可以很好地推广到任意 n-ary 树：

def is_locked(self):
    return self.locked and all(node.is_locked() for node in (self.left, self.right) if node)

n-ary 树可能具有可变序列属性 self.children 而不是 (self.left, self.right)。

Answer 2

对递归函数的每次新调用都会将该函数的新实例放入堆栈中，并带有自己的局部变量副本。

您正试图操纵 flag，就好像它是某个全局变量一样，但它对于每个被调用的 lock() 实例都是本地变量。请注意，这是一件好事 - 如果您有多个对象，它们当然不应该共享相同的 flag。将 flag 更改为 class 的属性在某些情况下仍然会出现问题。

您在正确的轨道上，尝试 return 结果，但是当您使用 self.lock() 进行递归调用时，这些调用将 return 该部分的结果因此，您应该像其他人建议的那样捕获 return 值并处理它。

即flag = self.lock(node_object.left) 而不是仅仅调用 self.lock(node_object.left)。我建议将 flag 重命名为 result，因为它确实是这样：一个保存结果的变量。

作为一项改进，而不是将结果分配给 flag / result 并在最后 returning 它 - 因为你没有在任何地方使用 flag除了 return 结果 - 您可以将所有 flag = <something> 语句更改为 return <something> 语句。没有禁止使用多个 return 语句的规则，尽管一些纯粹主义者可能出于特定原因不喜欢它。

如何在递归 python 函数中正确放置 return 值

How to rightly place a return Value in the recursive python function

python

binary-tree

python-3.x