python - 获取二叉树中第j层的第i个元素Python

Question

我写的方法是getNode和helper。由于某种原因它不起作用。这是代码。

Class 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)

运行后出现以下错误:

File "btree.py", line 33, in helper
    return arr[ind]
IndexError: list index out of range

Answer 1

它看起来基本上是正确的，问题是你的辅助函数正在递归地构建一个数组，但在每次迭代中它都试图在完成附加到数组之前返回第 i 个元素:

return arr[ind]

相反，您应该让助手不返回任何内容并简单地填充给定的数组，然后将 getNode 修改为:

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