Подсчет узлов бинарного дерева без рекурсии Python

Question

Я знаю, как сделать это рекурсивно:

def num_nodes(tree): 
if not tree.left and not tree.right: 
    return 1 
else: 
    return 1 + num_nodes(tree.left) + num_nodes(tree.right) 

Но как бы вы это не рекурсивно? Возникли проблемы с доступом к узлу, который находится справа от левого поддерева.

Answer 1

Вы можете сохранить узлы, которые вам нужно сделать в списке.

queue = [] 
count = 0 
queue.append(root) 
# Above is start of tree 

while(queue): 
    if queue[0].left: 
    queue.append(queue[0].left) 
    if queue[0].right: 
    queue.append(queue[0].right) 
    queue.pop(0) 
    count += 1 

который должен работать до тех пор, пока в вашем дереве нет никаких петель.