二叉树上广度优先搜索的空间复杂度是多少？

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)。

不过，我在分析解决方案的空间复杂度时遇到了麻烦。我从空间复杂度了解到，在分析空间复杂度时，你必须考虑从堆和栈分配的空间

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

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

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

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

Answer 1

考虑“完整”或“完美”二叉树：

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

在最后一次迭代中，队列将容纳树中大约一半的节点，因此复杂度为

O(n/2)

，与

O(n)

相同，因为常量被丢弃。