Есть задача - проверить, что в бинарном дереве все узлы имеют одинаковое значение.
И есть эталонное решение при помощи рекурсии:
class Solution {
public bool IsUnivalTree(TreeNode root) {
bool left_correct = root.left == null ||
(root.val == root.left.val && IsUnivalTree(root.left));
bool right_correct = root.right == null ||
(root.val == root.right.val && IsUnivalTree(root.right));
return left_correct && right_correct;
}
}
Работает... Но есть у меня сомнения, что в статье правильно указана сложность:
Time Complexity: O(N), where N is the number of nodes in the given tree.
Space Complexity: O(H), where H is the height of the given tree.
Моё видение такое: пространственная сложность должна быть тоже O(N), так как в худшем случае все элементы могут быть выстроены друг под другом и нужно учитывать и такой случай.
Но я что-то сомневаюсь... Расчёт худшего кейса это уже не нотация О-большое?
Это правильная логика, если нет, то почему?
Space Complexity: O(H)
, хотя мне кажется вполне резонно предположитьSpace Complexity: O(N)
если специфика дерева на входе не определена.