Действительно ли решение грубой силы «Сбалансированное двоичное дерево» 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). Так что в целом это максимум nlogn.
Если O(n²) достижимо, а мое доказательство плохое, может ли кто-нибудь предоставить конкретную форму дерева (или повторение), которая вызывает это?

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