计数二叉树的节点，而不递归的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 

只要你的树没有任何循环，它应该工作。