Получить i-й элемент на j-м уровне в двоичном дереве Python

Question

Методы, которые я написал, - это getNode и helper. По какой-то причине это не работает. Вот код класса Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def helper(self, level, ind, arr):
        if level == 0:
            arr.append(self)
        else:
            if self.left:
                self.left.helper(level-1, ind, arr)
            if self.right:
                self.right.helper(level-1, ind, arr)

        return arr[ind]

    def getNode(self, level, ind):
        arr = []
        return self.helper(level, ind, arr)





# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print(self.data),
        if self.right:
            self.right.PrintTree()

root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.insert(7)
root.insert(13)
root.PrintTree()

a = root.getNode(2, 2).data
print('Answer is: ', a)

После запуска я получаю следующую ошибку: Файл "btree.py", строка 33, в хелпере, возвращает arr [ind] IndexError: список индексов вне диапазона

Answer 1

Это выглядит в основном правильно, проблема в том, что ваша вспомогательная функция рекурсивно создает массив, но на каждой итерации она пытается вернуть i-й элемент до того, как он завершил добавление в массив:

return arr[ind]

Вместо этого у вас должен быть помощник, который ничего не возвращает и просто заполняет данный массив, а затем изменяет getNode так:

def getNode(self, level, ind):
    arr = []
    self.helper(level, ind, arr)
    return arr[ind]

Answer 2

Похоже, вы передаете пустой массив для arr, а затем пытаетесь получить доступ к его 3-му элементу (после выполнения некоторых рекурсивных вызовов, которые могут или не могут привести к добавлению некоторых вещей в arr - я ожидаючто если какой-либо из этих вызовов добавляет некоторые элементы, они не добавляют достаточно).

Я думаю, что вы пытаетесь сделать слишком много вещей одновременно - вместо того, чтобы ваша рекурсивная вспомогательная функция пыталась получитьN-й элемент массива (до его завершения), я бы сосредоточился на том, чтобы помощник просто отвечал за добавление объектов в массив в правильном порядке, а затем getNode проверял массив после всего помощникавызовы завершены.