6

这是水平顺序遍历的代码：

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)。这对我来说听起来不正确。请分享您的意见。

谢谢，

4

2 回答 2

9

如果您考虑一下，在具有 n 个节点的树中，您不可能在任何时候将超过 n 个节点放入队列中，因为任何节点都不会被排入队列两次。这给出了 O(n) 的直接上限。但是，这不是一个严格的界限，因为如果树是一个退化的链表，那么内存使用量将只是 O(1)。

您的 O(2 h ) 上限也是正确的，但它的上限较弱。在高度为 h 的树中，底层最多可以有2 个h节点，但不能保证确实如此。如果树是退化链表，高度为 O(n)，并且 O(2 h ) 的界限将指数地过度近似内存使用量。

因此，您的界限是正确的，但 O(n) 是一个更好的界限。

希望这可以帮助！

于 2013-11-01T03:25:37.663 回答
3

两者O(2^h)和O(n)都是正确的，前提是还提到空间复杂度是针对最坏情况而不是针对最佳情况的。

当没有提到空间复杂度是针对最坏情况还是最佳O2^h情况时，两者之间的混淆在于，因为最坏情况和最佳情况是不同的，并且可能会误导最佳情况。O(n)h

最坏情况（当树平衡时）：O(n)

当树平衡时，最后一层将具有最大节点数，即2^h. 对于平衡树，h将是log n。所以O(2^h)=> O(2 ^ (log n))=>O(n)

最佳情况（当树是退化链表时）：O(1)

当树是退化链表时，每一层最多有一个节点，因此在任何时间点，队列中最多有一个节点。

于 2018-10-10T17:35:22.513 回答