Проверка сбалансированности двоичного дерева

Я реализовал фрагмент кода C ++ ниже, чтобы проверить, сбалансировано ли двоичное дерево, то есть высота левого и правого поддеревьев отличается не более чем на 1. Однако я не уверен, является ли он эффективным, или неоднократно проверяет поддерево в плохой способ. Может кто-нибудь направить меня, пожалуйста?

 unordered_map <Node*, int>  height;
struct Node{
int key;
Node* left;
Node* right;
}
bool isBalanced(Node* root){
if (root == nullptr){
height[root] = -1;
return true;
}
if (!isBalanced(root->left)) return false;
if (!isBalanced(root->right)) return false;

height[root] = max(height[root->left], height[root->right]) + 1;return (abs(height[root->left] - height[root->right]) < 1);
}

3

Решение

Я постараюсь передать идею, используя псевдокод.

int CheckTreeHeight(Node root)
{
if(root == null) return 0; // Height of 0.

// Check if left is balanaced
int leftChildHeight = CheckTreeHeight(root.left);
if(leftChildHeight == -1) return -1; // Not Balanced

// Check if right is balanaced
int rightChildHeight = CheckTreeHeight(root.right);
if(rightChildHeight == -1) return -1; // Not Balanced

// Check if current node is balanced
int heightDifference = leftChildHeight - rightChildHeight;

if(Math.abs(heightDifference) > 1)
return -1; // not balanaced
else
return Math.max(leftChildHeight, rightChildHeight) + 1; // Return Height
}

bool IsBalanced(Node root)
{
if(CheckTreeHeight(root) == -1)
{
return false;
}
else
{
return true;
}
}

Этот алгоритм выполняет в O(n) сложность времени и O(H) космическая сложность, где h это высота дерева.

Как уже упоминалось автором алгоритма, идея состоит в том, что мы проверяем дочерние элементы корня (то есть left а также right) рекурсивно, пока мы не нашли неуравновешенный, куда мы возвращаемся -1,

С помощью этой техники мы немедленно возвращаемся, если любое из поддеревьев не сбалансировано.

Более подробную информацию об этой реализации вы можете найти в книге, упомянутой в ссылке ниже.

Ссылка
Взломать кодирование Интервью 6-е издание

3

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]