##############################
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 требует добавления списка. Есть ли способ заставить эту функцию работать без создания списка вне функции? т.е. напрямую возвращая список, сгенерированный рекурсивно?
Спрашивая, поскольку это часть задания для школы, и хотя он возвращает правильный вывод, он не проходит модульный тест: Непредвиденная ошибка: имя «список узлов» не определено.
Обычный способ сделать это — использовать вспомогательную функцию:
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
в качестве имен переменных, поскольку они являются встроенными функциями Python)
Источником проблемы является то, что вы пытаетесь использовать глобальную переменную nodelist
внутри get_nodes_in_range
функции. Ваш код работает, когда вы его запускаете, и не работает, когда вы его импортируете. Потому что __name__
не равно '__main__'
при импорте кода. Так работает Питон. Это ожидаемое и правильное поведение.
Я предлагаю следующий подход для решения проблемы.
# 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)