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

[Anonymous]

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

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

A обычное решение «грубой силы»:

• Для каждого узла вычислите высоту (слева) и высоту (справа)
• Если 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» заставляет VISITED* часть дерева иметь максимальную высоту O(log n). Это связано с тем, что наименее сбалансированное из сбалансированных деревьев имеет высоту O(log n) (простое доказательство с использованием последовательности Фибоначчи). И работа «на строку» не превышает O (n). Так что в целом это максимум O(nlogn). Но сетевой код (ссылка выше) говорит, что это O(n²). Я знаю, что технически, если алгоритм O(nlogn), то он также O(n²). Но я ищу «самую узкую границу большого О». Сорта не имеет смысла использовать нежесткую верхнюю границу сложности, иначе я бы просто сказал, что все мои алгоритмы - это O(n^n^n^n^n^n^n).
* Под посещенными я подразумеваю набор узлов, по которым мы рекурсивно работаем перед ранним выходом.
Если O(n²) достижимо, а мое доказательство плохое, может ли кто-нибудь предоставить конкретную форму дерева (или повторение), которая заставляет это (т. е. не строго, но хорошая эвристика будет заключаться в том, что мое решение занимает более нескольких секунд для дерева с 10 ^ 7 узлами, показывая, что это действительно не O (nlogn), поскольку обычные компьютеры выполняют 10 ^ 9 операций в секунду)? Или, может быть, этот сетевой код человека допустил ошибку?
Чтобы уточнить: я знаю, что мы можем достичь O(n) с обходом пост-заказа. Меня интересует, почему это плохое решение считается O(n²), а не O(nlogn).

Подробнее здесь: https://stackoverflow.com/questions/798 ... 2-with-ear