algorithm - 使用堆栈遍历树时如何跟踪树的深度？

Question

如果我有一个使用如下堆栈的树遍历算法:

input: root
push root onto stack
while stack not empty:
    pop current node off stack
    mark current as visited
    for each of current node's successors:
        if successor not visited:
            push successor onto stack

有没有一种简单的方法可以修改此算法以提供树的最大深度？如果我使用递归，我可以想到如何去做，但我有点卡住想如何使用堆栈方法来做。

Answer 1

您可以将节点及其深度压入堆栈，然后跟踪您目前看到的最大深度。

input: root
push (root, 0) onto stack
max_depth = 0
while stack not empty:
    pop current (node, depth) off stack
    if depth > max_depth:
        max_depth = depth
    mark current as visited
    for each of current node's successors:
        if successor not visited:
            push (successor, depth+1) onto stack

return max_depth