是否可以在不使用堆栈的情况下评估表达式树(前/后缀)？在学校的算法课上讲树时有这个问题。我的猜测是否定的。
最佳答案
是的，你可以。
做一个breadth first traversal树的(像搜索一样，但遍历所有树)。您可以使用向量/队列/列表以迭代方式执行此操作。
完成后，您可以向后遍历您在上一步中生成的列表/向量/队列。在每个点计算列表中节点的值。由于您已经访问了所有 child (您正在倒退)，您所要做的就是查找它们的值并在节点中应用指令。
关于algorithm - 在没有堆栈的情况下评估表达式树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33099058/