获取二叉树的大小(log n)

r1zhe5dt 于 2021-07-08 发布在 Java

关注(0)|答案(1)|浏览(292)

充分披露：这是家庭作业。
我被要求返回二叉树中的秩，经过一些编码后，我让它工作。但是由于我的代码没有被接受，我注意到代码应该在 O(log n) 拖慢这一步的罪魁祸首是我的尺寸法：

public int size(Node node){
    if (node != null) return (size(node.left) + 1 + size(node.right));
    return 0;
}

我调用它是为了得到比我需要查找的元素更小的所有元素的秩。
现在，我在google上搜索了一下，但是很明显，在logn时间里不可能得到bt的大小？
那我该怎么做呢？

Java data-structures binary-tree big-o time-complexity

来源：https://stackoverflow.com/questions/64987934/get-size-of-a-binary-tree-in-olog-n

1条答案

按热度按时间

rdlzhqv91#

对于只存储子节点的简单二叉树，不可能在o（log（n））时间内获得大小，因为有n个节点，必须对每个节点进行计数。然而，为什么要限制自己只生孩子呢？与许多数据结构一样，可以使用节点存储大小：

class Node {
    public Node left;
    public Node right;
    public int value;
    private int size; // initialize this to 1
}

然后，在插入节点时，增加遇到的每个节点的大小：

public void insert(int value) {
    // increment the size
    this.size++;
    if (value < this.value) {
        // obviously check for null as well and insert as appropriate
        this.left.insert(value);
    } else {
        this.right.insert(value);
    }
}

现在，您可以在o（1）时间内获得大小，因为每个节点都有它。

赞(0）回复(0）举报 2021-07-09

我来回答

获取二叉树的大小(log n)

1条答案

相关问题

热门标签

最新问答