clw*_*wen 7 algorithm data-structures
我想知道是否可以在仅使用O(1)空间的情况下以广度优先打印二叉树？
困难的部分是必须使用额外的空间来记忆下一个级别来遍历,并且随着n的增长而增长.
既然我们没有对时间部分进行任何限制,也许有一些低效(在时间上)可以实现这一目标的方法？
任何的想法？
这将取决于一些更细粒度的定义，例如边缘是否有反向链接。然后就很容易了，因为您只需沿着树上的反向链接即可。否则，我无法立即想出一种没有 O(lg节点数) 空间的方法，因为您至少需要记住“上面”的节点。
更新
哦等等，当然可以通过时空交易在 O(1)空间内完成。无论您想要在哪里进行反向链接，您都可以保存您的位置并执行 BFS，跟踪最近的节点，直到找到您的节点。然后备份到最近访问的节点并继续。
问题是，空间复杂度为 O(1)，时间复杂度为 O(n^2)。
另一个更新
假设我们已经到达节点 n_i，并且想要到达该节点的父节点，我们将其称为 wlg n_j。我们已经识别出显着的根节点n_0。
修改呼吸优先搜索算法，以便当它遵循有向边 (n_x,n_y) 时，存储传出或“传入”节点。因此，当您遵循 (n_x,n_y) 时，您将保存 n_x。
当您从 n_0 再次启动 BFS 时，可以保证（假设它确实是一棵树）在某个点，您将转换边 (n_j,n_i)。那时你会发现你回到了n_i。您已经存储了 n_j，因此您知道反向边是 (n_i,n_j)。
因此，您只需两个额外的单元即可获得单个回溯，一个用于 n_0，一个用于“已保存”节点。这是 O(1)
我不太确定 O(n^2) ——现在已经很晚了，而且这一天很艰难，所以我不想写证明。我确定它是 O((|N|+|E|)^2) 其中 |N| 和|E| 分别是顶点集和边集的大小。