具有时间复杂性的问题

Question

好，问题很简单，我们需要在完整的二叉树中找到所有节点的数量。

我已经尝试使用下面给出的方法解决问题，但是仍然了解时间复杂性。有些人同意为O（logN ^ 2），而另一些人说甚至比O（N）还多，所以也许O（NlogN）。请进行验证，并提出一些更好的方法来解决此问题。

int countNodes(TreeNode* root) {
        if(!root)  return 0;
        int hl=0, hr=0;
        TreeNode *l=root, *r=root;
        while(l) { hl++; l=l->left; }
        while(r) { hr++; r=r->right;}
        if(hl==hr) return pow(2, hl)-1;
        return 1 + countNodes(root->left)+countNodes(root->right);
    }

Answer 1

您可以简单地计算出左侧的项目数量和右侧的项目数量，并将其加总：

int countNodes(TreeNode* root) {
    if(!root)  return 0;
    return 1 + countNodes(root->left)+countNodes(root->right);
}

如果我们假设所有算法都可以在恒定时间内完成（实际上是这样，因为int具有固定的字长），它将最多导致3×n次调用（因为每片叶子都可以进行两次额外的调用，每次调用都为null），因此可以在线性时间内工作。

首先，您对计算最左边的项目和最右边的项目的优化是不正确的，因为如果是这种情况，并且节点在树中是唯一的，那么这意味着子代的数量仅仅是一个。即使您设法使该工作正常，也不会有所不同，因为如果子代数不是一个，我们还是需要通过递归来进行计算。

A complete二叉树意味着只有最后一层可以具有null，而不是节点。但是，这意味着在最后一层中最多会有⌊n/2⌋+ 1。我们可以在最后一层执行二进制搜索，以找出最后一层的停止位置，这确实会使它成为O（log ² n）：an O（log n）二进制搜索，但是每个查询都要花费O（h）的时间进行检查，并且由于树的高度随O（log n）缩放，因此我们得到O（log ² N）。我将其作为实现该目标的练习。