Оптимальный подсчет количества узлов в полном двоичном дереве ⇐ C++

[Anonymous]

Я рассматриваю задачу 222 LeetCode. Подсчет полных узлов дерева:

При наличии корня завершенного двоичное дерево, возвращает количество узлов в дереве.
Согласно Википедии, каждый уровень, за исключением, возможно, последнего, полностью заполнен полным двоичным деревом, и все узлы в последний уровень находится как можно дальше влево. Он может иметь от 1 до 2h узлов включительно на последнем уровне h.
Разработайте алгоритм, который работает с временной сложностью менее O(n).

Я нацелен на временную сложность O(log(n)), однако в в худшем случае, насколько я понимаю, когда на последнем уровне будет один узел, сложность будет O(n*log(n)). Но это не соответствует требуемому "меньше чем O(n)". Что мне здесь не хватает?
Анализ
Грубый подход к подсчету количества узлов в целом, который проходит через все дерево а подсчет количества встреченных узлов равен O(n), где n — количество узлов.
Чтобы улучшить этот процесс, мы могли бы использовать информацию, которую дерево является полным двоичным деревом и имеет уровни O(log(n)). Чтобы мы могли вычислить высоту слева и справа. Если они окажутся равными для корня поддерева, то это поддерево является полным двоичным деревом, а количество узлов имеет решение в замкнутой форме как 2^h-1, где h - высота поддерева.
В коде это будет выглядеть примерно так:

Код: Выделить всё

int findLeftHeight(BinaryTreeNode* root){
int leftHeight = 0;
while(root){
leftHeight += 1;
root = root->left;
}
return leftHeight;
}

int findRightHeight(BinaryTreeNode* root){
int rightHeight = 0;
while(root){
rightHeight += 1;
root = root->right;
}
return rightHeight;
}

int countCompleteNodes(BinaryTreeNode* root){
if(root == NULL){
return 0;
}
int lh = findLeftHeight(root);
int rh = findRightHeight(root);

if(lh == rh) return (1right);
}

Но для худшего случая, когда полное бинарное дерево имеет всего один узел на последнем уровне, причем количество уровней максимально допустимо для верхней границы n. Тогда кажется, что время, необходимое для подсчета, равно O(n*log(n)), потому что на каждом рекурсивном шаге мы вызываем как root->left, так и root->right. .
Что мне здесь не хватает?

Подробнее здесь: https://stackoverflow.com/questions/786 ... inary-tree