打印二叉树BFS的方式与O（1）空间 [英] Print binary tree in BFS fashion with O(1) space

问题描述

我在想，如果有可能，而只用O（1）空间广度优先的顺序打印二叉树？

I was wondering if it's possible to print a binary tree in breadth first order while using only O(1) space?

困难的部分是一个必须使用额外的空间记忆下一级遍历，并用正增长。

The difficult part is that one have to use additional space to memorize the next level to traverse, and that grows with n.

由于我们没有放置任何限制的一部分时间，也许有一些低效率（在时间上）的方式，可以做到这一点？

Since we haven't place any limitation on the time part, maybe there are some inefficient (in terms of time) ways that can achieve this?

你知道吗？

推荐答案

这是要依赖于一些更细致的定义，例如，如果边缘有反向链接。然后，它很容易，因为你可以按照一个返回链接了树。否则，我不能想办法做到这一点不为O（LG的的节点数<​​/ em>的）空间了手，因为你需要记住至少节点上面。

This is going to depend on some finer-grained definitions, for example if the edges have back-links. Then it's easy, because you can just follow a back link up the tree. Otherwise I can't think off hand of a way to do it without O(lg number of nodes) space, because you need to remember at least the nodes "above".

更新

哦，等等，当然也可以为O完成（1）的空格的具有时空交易。无处不在，你会想要做一个反向链接，您可以节省你的地方，做BFS，跟踪最新的节点，直到你找到你的。然后备份到最近访问节点，并继续进行。

Oh wait, of course it can be done in O(1) space with a space time trade. Everywhere you would want to do a back link, you save your place and do BFS, tracking the most recent node, until you find yours. Then back up to the most recently visited node and proceed.

但问题是，这是O（1）空间，但为O（n ^ 2）的时间。

Problem is, that's O(1) space but O(n^2) time.

另一个更新

让我们假设我们已经达到节点n_i，我们要达到这个节点，我们称之为WLG n_j的父母。我们已经确定了杰出的根节点n_0。

Let's assume that we've reached node n_i, and we want to reach the parent of that node, which we'll call wlg n_j. We have identified the distinguished root node n_0.

修改呼气优先搜索算法，这样，当它跟随有向边（n_x，n_y），传出或呼入节点被存储。因此，当你跟随（n_x，n_y），为您节省n_x。

Modify the breath-first search algorithm so that when it follows a directed edge (n_x,n_y), the efferent or "incoming" node is stored. Thus when you follow (n_x,n_y), you save n_x.

当你再次从n_0开始BFS，可以保证（假设它确实是一棵树），在某些时候，你会过渡的边缘（n_j，n_i）。在这一点上，你看到你回到n_i。你已经存储n_j，并让你知道反向边缘（n_i，n_j）。

When you start the BFS again from n_0, you are guaranteed (assuming it really is a tree) that at SOME point, you will transition the edge (n_j,n_i). At that point you observe you're back at n_i. You've stored n_j and so you know the reverse edge is (n_i,n_j).

因此​​，你只需要使用两个额外的电池，一个用于n_0，一个用于拯救节点单原路返回。这是O（1）

Thus, you get that single backtrack with only two extra cells, one for n_0 and one for the "saved" node. This is O(1)

我不那么肯定为O（n ^ 2） - 它的晚，它是一个艰难的一天，所以我不希望组成一个证明。我敢肯定，这是O（（| N | + | E |）^ 2）其中，| N |和| E |是顶点和边分别集合的大小。

I'm not so sure of O(n^2) -- it's late and it's been a hard day so I don't want to compose a proof. I'm sure it's O((|N|+|E|)^2) where |N| and |E| are the size of the sets of vertices and edges respectively.

这篇关于打印二叉树BFS的方式与O（1）空间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！