不使用附加内存的层级树遍历

Question

我知道对树进行顺序遍历的算法。 （我想每个人都知道这一点）该算法使用队列来存储树的节点。有没有不使用额外内存的算法？该算法一定不能使用递归（这样我们就可以使用堆栈）。

Answer 1

如果您可以在树的每个节点中存储一个额外的下一指针，该指针指向每个级别的级别顺序的下一个节点，那么您可以在恒定空间中进行级别顺序遍历。