以O(1)空间复杂度按BFS方式打印二叉树

Question

以O(1)空间复杂度按BFS方式打印二叉树

algorithmdata-structures

7

我在想是否有可能只使用O(1)空间打印二叉树的广度优先遍历结果？

难点在于需要使用额外的空间来记忆下一层需要遍历的节点，这个空间会随着n的增加而增加。

既然对时间没有任何限制，也许有一些效率低（就时间而言）但可以实现这一目标的方法？

您有什么想法吗？

- clwen

@Ted 这是一个可能出现在面试中的问题。 - clwen

4个回答

2

一个有趣的特殊情况是堆。

来自 heapq 文档：

堆是一种二叉树，其中每个父节点的值都小于或等于其任何子节点的值。此实现使用数组，其中对于所有 k，从零开始计数，heap[k] <= heap[2*k+1] 和 heap[k] <= heap[2*k+2]。为了比较，认为不存在的元素是无限的。堆的有趣属性是它的最小元素总是根 heap[0]。[由 François Pinard 解释]

如何在内存中表示树（数组的索引）：

                               0

              1                                 2

      3               4                5               6

  7       8       9       10      11      12      13      14

15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30

在这种情况下，数组中的节点已经按照广度优先顺序存储。

for value in the_heap:
    print(value)

在空间复杂度上是O(1)。

- jfs

1

我知道这严格来说不是问题的答案，但是可以通过递归迭代加深深度优先搜索（IDDFS）以O（d）空间访问树的节点，其中d是树的深度。当然，堆栈需要占用一定的空间。对于平衡树，d = O(lg n)，其中n是节点数。老实说，如果没有@Charlie Martin建议的反向链接，我真的看不出如何在恒定的空间中完成它。

- Fred Foo

-1

实现一个递归方法来获取给定层的树的所有节点是很容易的。因此，我们可以计算树的高度并获取每个级别的所有节点。这是树的层次遍历。但是，时间复杂度是O(n^2)。以下是Java实现(source)。

class Node 
{ 
    int data; 
    Node left, right; 
    public Node(int item) 
    { 
        data = item; 
        left = right = null; 
    } 
} 

class BinaryTree 
{ 
    Node root; 

    public BinaryTree() 
    { 
        root = null; 
    } 

    void PrintLevelOrder() 
    { 
        int h = height(root); 
        int i; 
        for (i=1; i<=h; i++) 
            printGivenLevel(root, i); 
    } 

    int Height(Node root) 
    { 
        if (root == null) 
           return 0; 
        else
        { 
            int lheight = height(root.left); 
            int rheight = height(root.right); 

        } 
    } 

    void PrintGivenLevel (Node root ,int level) 
    { 
        if (root == null) 
            return; 
        if (level == 1) 
            System.out.print(root.data + " "); 
        else if (level > 1) 
        { 
            printGivenLevel(root.left, level-1); 
            printGivenLevel(root.right, level-1); 
        } 
    }
}

- havij

这使用O（h）空间，其中h是树的高度。递归是使用调用堆栈实现的，这被视为辅助空间。 - kaya3

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Charlie Martin · Accepted Answer

这将取决于一些更精细的定义，例如边缘是否具有后向链接。如果是这样，那么很容易，因为您只需沿着树上的后向链接进行跟踪即可。否则，我想不到在不使用O（lg节点数）空间的情况下完成它的方法，因为您至少需要记住“上面”的节点。

更新

哦，等等，当然可以通过时间和空间的权衡在O（1）空间内完成。在您想要执行后向链接的每个位置，保存您的位置并执行BFS，跟踪最近的节点，直到找到您的节点。然后返回到最近访问的节点并继续。

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

另一个更新

假设我们已经到达节点ni，并且我们想要到达该节点的父节点，我们将称其为wlg nj。我们已经确定了特殊的根节点n0。

修改广度优先搜索算法，以便在遵循定向边（nx，ny）时存储传出或“传入”节点。因此，当您遵循（nx，ny）时，保存n_x。

当您再次从n0开始BFS时，您保证（假设它确实是一棵树）在某个时候，您将转换边（nj，ni）。在那一点上，您观察到您回到了ni。您已经存储了nj，因此您知道反向边是（ni，nj）。

因此，您可以使用仅两个额外单元的单个回溯，一个用于n0，另一个用于“保存”的节点。这是O（1）

我不太确定O（n ^ 2）-现在很晚了，今天很辛苦，所以我不想编写证明。我确定它是O（（| N | + | E |）^ 2），其中| N |和| E |分别是顶点和边的集合的大小。