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

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();
}

同样的空间复杂性也适用于我的树变异吗？我还没有生成一个测试用例，其中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)相同。