如何递归查找范围内 BST 中的节点，以及 return 完整列表？

Question

##############################
class Node:
    def __init__(self,value):
        self.left = None
        self.right = None
        self.val = value

###############################
class BinarySearchTree:
    def __init__(self):
        self.root = None

def print_tree(node): 
    if node == None:
        return
    print_tree(node.left)
    print_tree(node.right) 
    print(node.val)


#################################################
# Task 1: get_nodes_in_range function
#################################################  
def get_nodes_in_range(node,min,max):
    if node == None:
        return
    get_nodes_in_range(node.left, min, max)
    get_nodes_in_range(node.right, min, max)
    if min <= node.val <= max:
        nodelist.append(node.val)
    return nodelist
    


if __name__ == '__main__':
    BST = BinarySearchTree()
    BST.root = Node(10)
    BST.root.left = Node(5)
    BST.root.right = Node(15)
    BST.root.left.left = Node(2)
    BST.root.left.right = Node(8)
    BST.root.right.left = Node(12)
    BST.root.right.right = Node(20)
    BST.root.right.right.right = Node(25)
    nodelist = []
    print(get_nodes_in_range(BST.root, 6, 20))

我的 get_nodes_in_range 函数需要附加一个列表。有没有办法在不在函数外部创建列表的情况下使这个函数工作？ IE。直接返回递归生成的列表？

询问，因为这是学校作业的一部分，虽然它 returns 是正确的输出，但未通过单元测试：意外错误：名称 'nodelist' 未定义。

Answer 1

一种常用的方法是使用辅助函数：

def get_nodes_in_range(node, lo, hi):
    res = []
    get_nodes_in_range_helper(node, lo, hi, res)
    return res

然后调整 get_nodes_in_range_helper 函数以附加到 res:

def get_nodes_in_range_helper(node, lo, hi, res):
    if node == None:
        return

    get_nodes_in_range_helper(node.left, lo, hi, res)
    get_nodes_in_range_helper(node.right, lo, hi, res)

    if lo <= node.val <= hi:
        res.append(node.val)

（注意：使用 min/max 作为变量名可能不是一个好主意，因为它们是 built-in Python 函数）

Answer 2

问题的根源是您试图在 get_nodes_in_range 函数中使用全局变量 nodelist。您的代码在运行时有效，而在导入时失败。因为导入代码时 __name__ 不等于 '__main__' 。这就是 Python 的工作原理。这是预期的正确行为。

我建议采用以下方法解决问题。

# just for convinience
def create_bst():
    ans = BinarySearchTree()
    ans.root = Node(10)
    ans.root.left = Node(5)
    ans.root.right = Node(15)
    ans.root.left.left = Node(2)
    ans.root.left.right = Node(8)
    ans.root.right.left = Node(12)
    ans.root.right.right = Node(20)
    ans.root.right.right.right = Node(25)
    return ans

# fix - create a list to store results inside the function
def get_nodes_in_range_1(node, min_value, max_value):

    ans = list()
    if node is None:
        return ans
    if min_value <= node.val <= max_value:
        ans.append(node.val)
    ans.extend(get_nodes_in_range_1(node.left, min_value, max_value))
    ans.extend(get_nodes_in_range_1(node.right, min_value, max_value))

    return ans


if __name__ == '__main__':

    bst = create_bst()

    nodes_in_range_1 = get_nodes_in_range_1(bst.root, 6, 20)
    print(nodes_in_range_1)

如何递归查找范围内 BST 中的节点，以及 return 完整列表？

How do I recursively find nodes in a BST within a range, and return a full list?

python

list

recursion

binary-search-tree