Оптимальный подсчет количества узлов в полном двоичном дереве
Я смотрю на задачу LeetCode 222. Подсчитайте полные узлы дерева:
Учитывая
rootполного двоичного дерева, верните количество узлов в дереве.Согласно Википедии, каждый уровень, за исключением, возможно, последнего, полностью заполнен полным двоичным деревом, и все узлы на последнем уровне расположены максимально слева. Он может иметь узлы от
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<int>* root){
int leftHeight = 0;
while(root){
leftHeight += 1;
root = root->left;
}
return leftHeight;
}
int findRightHeight(BinaryTreeNode<int>* root){
int rightHeight = 0;
while(root){
rightHeight += 1;
root = root->right;
}
return rightHeight;
}
int countCompleteNodes(BinaryTreeNode<int>* root){
if (root == NULL){
return 0;
}
int lh = findLeftHeight(root);
int rh = findRightHeight(root);
if (lh == rh) return (1<<lh)-1;
return 1 + countCompleteNodes(root->left) + countCompleteNodes(root->right);
}
Но в худшем случае, когда полное бинарное дерево имеет только один узел на последнем уровне, причем количество уровней максимально допустимо для верхней границы n. Тогда кажется, что время, необходимое для подсчета, равно O(n*log(n)), потому что на каждом шаге рекурсии мы вызываем как root->left, так и root->right.
Что мне здесь не хватает?
Целевая временная сложность меньше O(n), а не O(log(n)), поэтому, например, будет учитываться O(log(n)^2).
По крайней мере один из дочерних элементов завершен, поэтому «настоящая» рекурсия выполняется только в одном дочернем элементе.
Ответы 1
Тогда кажется, что время, необходимое для подсчета, равно O(n*log(n)), потому что на каждом шаге рекурсии мы вызываем как
root->left, так иroot->right.
Но учтите, что по крайней мере один из этих двух рекурсивных вызовов будет иметь lh == rh. Не может случиться, что это неверно для обоих поддеревьев, поскольку это будет означать, что двоичное дерево не является полным. Например, здесь это будет ложно для обоих поддеревьев 𝐴 и 𝐵:
_ * _
/ \
A B
/ \ / \
* * * *
/ \ /
* * *
... которое не является полным двоичным деревом.
В заключение, несмотря на то, что выполняются два рекурсивных вызова, мы можем быть уверены, что по крайней мере один из них не будет иметь более глубоких рекурсивных вызовов, поэтому он будет выполняться с временной сложностью O(1). Оставшийся может иметь более глубокие рекурсивные вызовы, но всегда по одному пути, сужающемуся до места, где нижний слой имеет самый правый лист.
Хорошо, это означает, что в конечном итоге мы будем выполнять вызовы O(log(n)) примерно на высоте дерева, а это значит, что это O((log(n))^2).
Да, и это сублинейно.
Правильно ли вы оценили свою оптимизацию для использования функций findLeftHeight/findRightHeight? Я не уверен, что в лучшем или общем случае это на самом деле быстрее.