java - 使用队列的层级遍历遍历的空间复杂度

这是遍历级别的代码:

public void bfsTraveral() {
    if (root == null) {
        throw new NullPointerException("The root cannot be null.");
    }
    int currentLevelNodes = 0;
    int nextLevelNodes = 0;

    final Queue<TreeNode> queue = new LinkedList<TreeNode>();
    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)是一个更好的界限。

希望这可以帮助!