Как рекурсивно найти узлы в BST в пределах диапазона и вернуть полный список?

##############################
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 требует добавления списка. Есть ли способ заставить эту функцию работать без создания списка вне функции? т.е. напрямую возвращая список, сгенерированный рекурсивно?

Спрашивая, поскольку это часть задания для школы, и хотя он возвращает правильный вывод, он не проходит модульный тест: Непредвиденная ошибка: имя «список узлов» не определено.

Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
1
0
35
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Обычный способ сделать это — использовать вспомогательную функцию:

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)

Другие вопросы по теме