Действительно ли решение грубой силы «Сбалансированное двоичное дерево» O (n ^ 2) с ранним выходом? ⇐ Python

[Anonymous]

Я рассматриваю классическую задачу «сбалансированного двоичного дерева» (стиль LeetCode 110):

Для двоичного дерева определите, сбалансировано ли оно по высоте.
Двоичное дерево является сбалансированным по высоте, если для каждого узла высоты левого и правого поддеревьев отличаются не более чем на 1.

Распространенное решение «грубой силы»:

• Для каждого узла вычислите высоту (слева) и высоту (справа)
• Если abs(left-right) > 1, верните false
• В противном случае выполните рекурсию на левых и правых дочерних элементов

Пример Python:

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

class Solution:
def isBalanced(self, root):
if not root:
return True

left = self.height(root.left)
right = self.height(root.right)

if abs(left - right) > 1:
return False

return self.isBalanced(root.left) and self.isBalanced(root.right)

def height(self, node):
if not node:
return 0

return 1 + max(self.height(node.left), self.height(node.right))

Но свойство «коэффициент баланса ≤ 1» заставляет ПОСЕЩЕННУЮ часть дерева иметь максимальную высоту O(log n). И работа «на строку» не превышает O (n). Так что в целом это максимум O(nlogn). Но сетевой код (ссылка выше) говорит, что это O(n²).
Если O(n²) достижимо, а мое доказательство плохое, может ли кто-нибудь предоставить конкретную форму дерева (или повторение), которая вызывает это? Или, может быть, этот сетевой код человека допустил ошибку?
Чтобы уточнить: я знаю, что мы можем достичь O(n) с обходом пост-заказа. Меня интересует, почему это плохое решение считается O(n²), а не O(nlogn).

Подробнее здесь: https://stackoverflow.com/questions/798 ... early-exit