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

Question

Я выполнил приведенный ниже код 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); 
} 

Answer 1

Я попытаюсь передать идею с использованием псевдокода.

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.

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

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

Ссылка
Cracking the Coding Interview 6th Edition