Сомневаюсь в отношении функции проверить, сбалансировано ли дерево или нет?

Question

Я прочитал в книге под названием «Coding Interview Cracked», чтобы проверить, сбалансирован ли BST или нет, просто выясните разницу между максимальной и минимальной высотой, но я не уверен, что она на 100% правильная. Хотя я не могу найти контр-тестовый случай.

Может ли кто-нибудь подтвердить, является ли этот подход правильным или нет.

Для проверки, сбалансировано ли дерево.

|MaxHieght(root) - MinHieght(root)| <=1
   return true
else return false

Answer 1

С учетом определения сбалансированности (из вики Педиаса)

Коэффициент баланса узла - высота его левого поддерева минус высота его правого поддерева (иногда противоположного) и узла с коэффициент баланса 1, 0 или -1 считается сбалансированным. Узел с любым другой фактор баланса считается несбалансированным и требует перебалансировки дерево. Коэффициент баланса либо хранится непосредственно в каждом узле, либо вычисляется из высот поддеревьев.

Это кажется правильным. Поскольку minHeight и maxHeight будут равны высоте любой из сторон, похоже, что определение имеет значение

Answer 2

Вы также можете попробовать этот способ, если хотите.

bool isBalanced(node curPtr)
{
        static int heightLeft,heightRight; //Need to save previous return value

        if ( !curPtr )
        {
                return 0;
        }

        heightLeft  = isBalanced(curPtr->lChild);
        heightRight = isBalanced(curPtr->rChild);

        ++heightLeft;   // Height of the Tree should be atleast 1 ( ideally )
        ++heightRight;


        return ( ( ( heightLeft - heightRight ) == 0 ) || (( heightRight - heightLeft ) == 0 ) );
}

HTH