Решение Leetcode для сбалансированного двоичного дерева


Сложный уровень Легко
Часто спрашивают в Амазонка Google Microsoft
массив

A бинарное дерево является сбалансированным по высоте, если разница высот левого и правого поддерева каждого узла в дереве не превышает 1. В этой задаче мы собираемся проверить сбалансированное двоичное дерево.

Решение Leetcode для сбалансированного двоичного дерева

Пример

             2
        
          / 
    
        1

      /
 
    4
Not balanced
     1

  /     \

2         3
Balanced

Подход

Интуитивно понятно, что для каждую узел в двоичном дереве, мы можем проверить, соответствуют ли левое и правое поддеревья требуемому условию. Это "Грубая силаМетод.

Но, чтобы проверить, сбалансировано ли дерево, подход может быть улучшен на основании Время и пространство сложности.

Мы придерживаемся такого подхода, что решаем проблему в Bottom-Up манера. Проверить, являются ли поддеревья узла самим сбалансированным двоичным кодом. деревья(или нет) и одновременно получить высоту двоичного дерева, которую можно обобщить с помощью рекурсии.

Алгоритм (грубая сила)

  1. Начните с корня и продолжайте обход двоичного дерева до тех пор, пока корень становится NULL,
  2. Получите высоту левого и правого поддеревьев, используя высота() функция
    • Если разница больше чем '1':
      • вернуть ложь. Поскольку дерево не удовлетворяет условию баланса
    • Рекурсивно проверять условие баланса для левого и правого поддеревьев
  3. Распечатать результат

Алгоритм (Оптимальный)

  1. Если дерево пустой, можно сказать, сбалансировано. Если нет, мы можем выполнить другие шаги:
  2. Создайте вспомогательную функцию для возврата «высота”Текущего поддерева, используя рекурсию.
  3. Функция высоты вернет:
    • -1, когда это несбалансированное дерево
    • высота в противном случае.
  4. Если поддерево имеет левое или правое поддерево неуравновешенный, или их высота отличается более чем на «1», верните -1.
  5. В противном случае верните высоту этого поддерева как: 1 + max (left_height, right_height)

Реализация

Программа C ++ для решения Leetcode для сбалансированного двоичного дерева

Метод грубой силы

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};


int height(treeNode* root)
{
    if(root == NULL)
        return 0;
    return max(height(root->left) , height(root->right)) + 1;
}


bool balanced(treeNode* root)
{
    if(root == NULL)
    return true;

    int l = height(root->left) , r = height(root->right);
    //calling height function at every node
    if(abs(l - r) > 1)
        return false;

    return balanced(root->left) && balanced(root->right);
}


int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(2);
    root->left->left = new treeNode(4);
    
    if(balanced(root))
        cout << "Balanced" << '\n';
    else
        cout << "Not Balanced" << '\n';
    return 0;
}

Оптимальный метод

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};


int height(treeNode* root)
{
    if(root == NULL)
        return 0;
    int l = height(root->left);
    int r = height(root->right);
    if(l == -1 || r == -1 || abs(l - r) > 1)
        return -1;
    return max(l , r) + 1;
}


bool balanced(treeNode* root)
{
    if(root == NULL)
        return true;

    return (height(root) != -1);
}


int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(2);
    root->left->left = new treeNode(4);

    if(balanced(root))
        cout << "Balanced" << '\n';
    else
        cout << "Not Balanced" << '\n';
    return 0;
}
Not Balanced

Java-программа решения Leetcode для сбалансированного двоичного дерева

Грубая сила

import java.lang.Math;

class treeNode
{
    int value;
    treeNode left, right;

    public treeNode(int x)
    {
        value= x;
        left = right = null;
    }
}

class balanced_binary_tree
{
    public static int height(treeNode root)
    {
        if(root == null)
            return 0;
        return Math.max(height(root.left) , height(root.right)) + 1;
    }


    public static boolean balanced(treeNode root)
    {
        if(root == null)
            return true;

        int l = height(root.left) , r = height(root.right);
        if(Math.abs(r - l) > 1)
            return false;
        return balanced(root.left) && balanced(root.right);
    }


    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(3);

        if(balanced(root))
            System.out.println("Balanced");
        else
            System.out.println("Not Balanced");
    }
}

Оптимальный метод

import java.lang.Math;

class treeNode
{
    int value;
    treeNode left, right;

    public treeNode(int x)
    {
        value= x;
        left = right = null;
    }
}

class balanced_binary_tree
{
    public static int height(treeNode root)
    {
        if(root == null)
            return 0;

        int l = height(root.left);
        int r = height(root.right);

        if(l == -1 || r == -1 || Math.abs(l - r) > 1)
            return -1;

        return Math.max(l , r) + 1;
    }


    public static boolean balanced(treeNode root)
    {
        if(root == null)
            return true;

        return (height(root) != -1);
    }


    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.left.left = new treeNode(4);

        if(balanced(root))
            System.out.println("Balanced");
        else
            System.out.println("Not Balanced");
    }
}
Not Balanced

Анализ сложности решения Leetcode для сбалансированного двоичного дерева

Сложность времени

Метод грубой силы имеет временную сложность О (Н * Н), в худшем случае (перекос дерева). Однако оптимальный подход работает в НА) время, поскольку мы делаем только один проход.

Космическая сложность

O (N) в обоих случаях, поскольку рекурсия использует вспомогательное пространство стека.