Высота бинарного дерева - итеративная

Question

Это всегда делает только один цикл while:

def height(self):
    if self.root is None:
        return 0
    height = -1
    q = self.Queue()
    q.enqueue(self.root)
    while not q.is_empty():
        size = self.__len__()
        height += 1
        while size > 0:
            node = q.dequeue()
            if node.left is not None:
                q.enqueue(node.left)
            if node.right is not None:
                q.enqueue(node.right)
            size -= 1
    return height

У вас есть другая идея (или идея, как изменить этот код), чтобы вернуть правильную высоту двоичного дерева?

len - это число всех узлов в дереве, self.Queue - это подкласс класса с высотой метода.

Answer 1

Проблема в том, что в части кода

size = self.__len__()
while size > 0:
    # [...]
    size -= 1

количество выполнений тела цикла равно количеству узлов в целом дереве, а это не то, что вам нужно.

Вместо этого вы хотите

size = len(q)