在二叉树上进行广度优先搜索的 space 复杂度是多少？

Question

这是我的 Java 使用广度优先搜索逐层打印二叉树的解决方案（有效！！）

public void printByLevel() {
    System.out.print("Elements By Level:");
    if(overallRoot!= null) {
        Queue<IntTreeNode> bfs = new LinkedList<IntTreeNode>();
        bfs.add(overallRoot);
        while(!bfs.isEmpty()) {
            IntTreeNode root = bfs.remove();
            System.out.print(" " + root.data);
            if(root.left!=null) 
                bfs.add(root.left);
            if(root.right!=null)
                bfs.add(root.right);
        }
    }
    System.out.println();
}

我知道广度优先搜索算法会访问树中的所有节点，因此算法的时间复杂度将为 O(n)。

不过，我在分析 space 解决方案的复杂性时遇到了问题。我从中了解到，在分析space复杂度时，你必须考虑到你从堆中分配的space和堆栈

在这里，我没有进行任何递归调用，因此 space 复杂度将只是我为广度优先搜索队列分配的 space。我从这里读到 BFS Complexity 广度优先搜索的 space 复杂度是 O(V)，其中 V 是顶点数。

同样的 space 复杂性是否适用于我的树变体？我还没有生成一个测试用例，其中 BFS 队列将保存树中的所有节点。即使二叉树退化为链表，就像我从 得到的下图所示，其中对树的正常操作需要 O(n) 时间和 O(n) space，BFS队列最多包含 1 个元素。

    1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              ...`

谁能给我一个测试用例，其中 BFS 队列将保存树中的所有节点，证明 space 复杂度为 O(n)？

Answer 1

考虑 "full" 或 "perfect" 二叉树：

     .
   / .
  0  .
 / \ .
0    .
 \ / .
  0  .
   \ .
     .

在最后一次迭代中，队列将包含树中大约一半的节点，因此复杂度为O(n/2)，与O(n)相同。