这是级别顺序遍历的代码：

public void bfsTraveral() {

if (root == null) {

throw new NullPointerException("The root cannot be null.");

}

int currentLevelNodes = 0;

int nextLevelNodes = 0;

final Queue queue = new LinkedList();

queue.add(root);

currentLevelNodes++;

while(!queue.isEmpty()) {

final TreeNode node = queue.poll();

System.out.print(node.element + ",");

currentLevelNodes--;

if (node.left != null) { queue.add(node.left); nextLevelNodes++;}

if (node.right != null) { queue.add(node.right); nextLevelNodes++;}

if (currentLevelNodes == 0) {

currentLevelNodes = nextLevelNodes;

nextLevelNodes = 0;

System.out.println();

}

}

在我看来,空间复杂度应为O(2 ^ h),其中h是树的高度,这仅仅是因为它是执行期间队列可达到的最大大小.在互联网上,我发现空间复杂度为O(n).这听起来不对我.请分享您的意见.

谢谢,

解决方法:

如果你考虑一下,在一个有n个节点的树中,没有办法在任何时候都能让n个节点进入队列,因为没有节点会被排队两次.这给出了O(n)的直接上界.但是,这不是一个严格的限制,因为如果树是退化链表,那么内存使用将只是O(1).

你的O(2h)的上限也是正确的,但它是一个较弱的上界.在高度为h的树中,底层最多可以有2h节点,但不能保证实际情况如此.如果树是退化链表,则高度为O(n),并且O(2h)的界限将以指数方式过度增加内存使用量.

因此,你的界限是正确的,但O(n)是一个更好的界限.

希望这可以帮助！

标签：space-complexity,java,data-structures,big-o,binary-tree

来源： https://codeday.me/bug/20190831/1777861.html