如果我有一个使用这样的堆栈的树遍历算法:
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
有没有一种简单的方法可以修改这个算法以获得树的最大深度?如果我使用递归,我可以想到如何做到这一点,但我有点难以思考如何使用堆栈方法来做到这一点。
最佳答案
您可以将节点及其深度压入堆栈,然后跟踪迄今为止您所看到的最大深度。
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
关于algorithm - 使用堆栈遍历树时如何跟踪树的深度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47467431/