java – 使用队列进行遍历遍历的级别顺序的空间复杂性

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java – 使用队列进行遍历遍历的级别顺序的空间复杂性，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1241字，纯文字阅读大概需要2分钟。

内容图文

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

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)是一个更好的界限.

希望这可以帮助！

内容总结

以上是互联网集市为您收集整理的java – 使用队列进行遍历遍历的级别顺序的空间复杂性全部内容，希望文章能够帮你解决java – 使用队列进行遍历遍历的级别顺序的空间复杂性所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端