在二叉树上进行广度优先搜索的空间复杂度是多少？-Java 学习之路

这是我的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 Complexity了解到，在分析空间复杂性时，您必须考虑从堆和堆栈分配的空间

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

相同的空间复杂度是否适用于我的树变化？我还没有生成一个测试用例，其中BFS队列将保存树中的所有节点 . 即使二进制树退化为链接列表，如下图所示，我从BST获得，其中树上的正常操作需要O（n）时间和O（n）空间，BFS队列将保留最多1个元素 .

任何人都可以给我一个测试用例，其中BFS队列将保存树中的所有节点，证明空间复杂度是O（n）？

1 回答

3
考虑“完整”或“完美”二叉树：
```
.
   / .
  0  .
 / \ .
0    .
 \ / .
  0  .
   \ .
     .
```
在最后一次迭代中，队列将保留树中大约一半的节点，因此复杂度为 O(n/2) ，这与 O(n) 相同 .
回复于 2024-04-29T13:19:58+08:00

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

1 回答

相关问题