对 BST 中的递归感到困惑 python

Question

我试图理解二元函数中的递归调用 is_bst。该函数的目标是检查树是否为二叉搜索树。请注意，这只是完整功能的摘录。我试图了解 is_bst 函数中的这段代码 is_bst_l, min_l, max_l = is_bst(node.left) 发生了什么。 is_bst 函数 return (True, None, None)，我试图通过递归地遍历函数来弄清楚函数是如何得出 return 值的。 is_bst 函数将 parse_tuple 函数的二叉树节点作为输入。例如，当我尝试在 is_bst 函数外解压缩这行代码 is_bst_l, min_l, max_l = node.left 时，我得到 TypeError: cannot unpack non-iterable TreeNode object，但在函数内，我没有收到错误。我的问题是

is_bst 函数中递归发生的事情。
如何在 is_bst 函数中不获取 unpack TypeError。

`

#Tree Class
class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

#function converts a turble to a binary tree
 def parse_tuple(data):
    # print(data)
    if isinstance(data, tuple) and len(data) == 3:
        node = TreeNode(data[1])
        node.left = parse_tuple(data[0])
        node.right = parse_tuple(data[2])
    elif data is None:
        node = None
    else:
        node = TreeNode(data)
    return node

函数检查树是否为二叉搜索树。

def remove_none(nums):
return [x for x in nums if x is not None]

def is_bst(node):
    if node is None:
        return True, None, None
    
    is_bst_l, min_l, max_l = is_bst(node.left)
    is_bst_r, min_r, max_r = is_bst(node.right)
    is_bst_node = (is_bst_l and is_bst_r and 
              (max_l is None or node.key > max_l) and 
              (min_r is None or node.key < min_r))
#     print('Minkey left: ', min_l, 'Nodekey :', node.key, 'Maxkey left: ',min_r)
#     print('Minkey left: ', max_l, 'Nodekey :', node.key, 'Maxkey left: ',max_r)
    min_key = min(remove_none([min_l, node.key, min_r]))
    max_key = max(remove_none([max_l, node.key, max_r]))
    
    # print(node.key, min_key, max_key, is_bst_node)
        
    return is_bst_node, min_key, max_key

#函数调用

my_tuple= ((None,3,None),2,(None,5,None))
node = parse_tuple(my_tuple)

Answer 1

如果对每个节点都递归，则树是 BST：

它的左树如果存在就是二叉搜索树
它的右树如果存在就是BST
左树的最大值，如果存在，必须小于节点的值
右树的最小值，如果存在，必须大于节点的值

因此，将 return 值转换为三个值的元组是有意义的：

我是 BST 吗？
我的子树中最小的节点是什么
我的子树中最大的节点是什么。

Answer 2

该函数正在返回当前节点左侧和右侧的最大和最小键（除了 True/False 检查的结果）。它的递归从左节点和右节点组装这些键/有效性状态，创建需要管理（即排除）None 来自子节点返回值的结果。

这太复杂了，可能不值得你花时间去分析和理解。

我想你会发现这个更简单一些：

def is_bst(node,minKey=None,maxKey=None):
    if node is None: return True
    if minKey is not None and node.key<=minKey: return False
    if maxKey is not None and node.key>=maxKey: return False
    if not is_bst(node.left,minKey,self.key):   return False
    if not is_bst(node.right,self.key,maxKey):  return False
    return True

Answer 3

当is_bst(node.left)或is_bst(node.right) returns "None" for max_l,_min_l or max_r,min_r 发生以下情况:

条件 = (max_l 是 None) 或 (node.key > max_l)
条件 1 : (max_l 是 None)
条件 2 : (node.key >max_l)

案例一： is_bst_l, min_l, max_l = is_bst(真,None,None)

条件=条件1或条件2
condition = True 或 condition2 将不会被处理 因为 condition1 为“False”
condition = True 因为 condition1

案例2： is_bst_l, min_l, max_l = is_bst(True,1,1)

条件=条件1或条件2
condition = False 或 condition2 将被处理 因为 condition1 不是“True”
condition = True 因为 condition2

对 BST 中的递归感到困惑 python

Confusion about recursion in a BST python

python

recursion

binary-tree

binary-search-tree