Какова сложность времени выполнения этого алгоритма? И как вы делаете анализ для этого?
— Следующие lowestCommonAncestor Функция находит самого низкого общего предка из двух узлов, p а также qв двоичном дереве (при условии, что оба узла существуют и все значения узлов уникальны).
class Solution {
public:
bool inBranch(TreeNode* root, TreeNode* node)
{
if (root == NULL)
return false;
if (root->val == node->val)
return true;
return (inBranch(root->left, node) || inBranch (root->right, node));
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL)
return NULL;
if (root->val == p->val || root->val == q->val)
return root;
bool pInLeftBranch = false;
bool qInLeftBranch = false;
pInLeftBranch = inBranch (root->left, p);
qInLeftBranch = inBranch (root->left, q);
//Both nodes are on the left
if (pInLeftBranch && qInLeftBranch)
return lowestCommonAncestor(root->left, p, q);
//Both nodes are on the right
else if (!pInLeftBranch && !qInLeftBranch)
return lowestCommonAncestor(root->right, p, q);
else
return root;
}
};
Решение
Каждый раз, когда вы звоните inBranch(root, node), вы добавляете O (# потомков root) (Увидеть временная сложность поиска двоичного дерева). Я буду предполагать, что двоичное дерево сбалансировано для первого вычисления временной сложности, а затем рассмотрим наихудший сценарий, когда дерево не сбалансировано.
Сценарий 1: сбалансированное дерево
Количество потомков узла будет примерно вдвое меньше, чем у его родителя. Поэтому каждый раз, когда мы повторяем, звонки inBranch будет вдвое дороже. Допустим, N — общее количество узлов в дереве. В первом звонке lowestCommonAncestor, мы ищем все N узлов. В последующих звонках мы ищем левую или правую половину и так далее.
O (N + N / 2 + N / 4 …) все так же, как O (N).
Сценарий 2: Несбалансированное дерево
Скажем, это дерево очень неуравновешено таким образом, что все дети находятся на левой стороне:
A
/
B
/
C
/
etc...
Число потомков уменьшается только на 1 для каждого уровня рекурсии. Поэтому сложность нашего времени выглядит примерно так:
O (N + (N-1) + (N-2) + … + 2 + 1), который эквивалентно O (N ^ 2).
Есть ли способ лучше?
Если это дерево двоичного поиска, мы можем сделать так же, как O (path_length (p) + path_length (q)). Если нет, вам всегда нужно будет пройти по всему дереву хотя бы один раз: O (N), чтобы найти пути к каждому узлу, но вы все равно можете улучшить свой наихудший сценарий. Я оставлю это вам, чтобы выяснить фактический алгоритм!
Другие решения
В худшем случае двоичное дерево представляет собой список длины N где каждый узел имеет не более одного дочернего p а также q один и тот же листовой узел. В этом случае у вас будет время работы O(N^2): Ты звонишь inBranch (во время выполнения O(N)) на каждом узле на пути вниз по дереву.
Если двоичное дерево сбалансировано, это становится O(N log(N)) с N узлы, как вы можете соответствовать O(2^K) узлы в дерево глубины K (и рекурсировать максимум K раз): Нахождение каждого узла O(N), но вы делаете это максимум log(N) раз.
Обратите внимание, что гораздо лучший алгоритм найдет каждый узел один раз и сохранит список путей вниз по дереву, а затем сравнит пути. Поиск каждого узла в дереве (если он не отсортирован) — это наихудший случай O(N), список сравнения также O(N) (несбалансированный случай) или O(log(N)) (сбалансированный случай), поэтому общее время работы O(N), Вы могли бы сделать еще лучше на отсортированном дереве, но это, очевидно, здесь не дано.