Проблема со сложностью времени

Question

Хорошо, проблема довольно проста. Нам нужно найти количество всех узлов в полном бинарном дереве.

Я попытался решить вопрос, используя приведенный ниже подход, но все еще имея понимание времениСложность.Некоторые соглашаются как O (logN ^ 2), тогда как другие говорят, что это даже больше, чем O (N), поэтому O (NlogN) может быть.Kind Verify, а также предложите несколько лучших подходов для решения этой проблемы.

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 s вместо узлов.Но это означает, что в последнем слое будет не более ⌊n / 2⌋ + 1 .Мы можем выполнить бинарный поиск на последнем слое, чтобы выяснить, где последний слой останавливается, и это действительно сделает его O (log ² n) : O (logn) для бинарного поиска, но для каждого запроса требуется O (h) времени для проверки, и поскольку высота дерева масштабируется с O (log n) , мытаким образом получим O (log ² n) .Я оставляю это как упражнение для реализации этого.