Հավասարակշռված Երկուական ծառի Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Google Microsoft
Դասավորություն

A երկուական ծառ բարձրության վրա հավասարակշռված է, եթե ծառի յուրաքանչյուր հանգույցի ձախ և աջ ենթատեսակի բարձրությունների տարբերությունը առավելագույնը 1. Այս խնդրում մենք պատրաստվում ենք ստուգել հավասարակշռված երկուական ծառի առկայությունը:

Հավասարակշռված Երկուական ծառի Leetcode լուծում

Օրինակ

             2
        
          / 
    
        1

      /
 
    4
Not balanced
     1

  /     \

2         3
Balanced

Մոտեցում

Ինտուիտիվ է մտածել, որ ամեն մի հանգույց երկուական ծառի մեջ, մենք կարող ենք ստուգել, ​​թե ձախ և աջ ենթատեսակները հետևում են պահանջվող պայմանին: Դա «Ամենակոպիտ բռնությունների կիրառումը»Մեթոդը:

Բայց որպեսզի ծառը հավասարակշռված լինի ստուգելու համար, մոտեցումը կարելի է բարելավել այն հիմքի վրա Timeամանակ և տարածություն բարդությունները

Մենք հետևում ենք այնպիսի մոտեցման, որ խնդիրը լուծում ենք ա Bottom-Up եղանակով Ստուգեք ՝ արդյոք հանգույցի ենթա ծառերը ինքնին հավասարեցված երկուական են ծառ(կամ ոչ) և միաժամանակ ձեռք բերել երկուական ծառի բարձրությունը, որը կարող է ընդհանրացվել `օգտագործելով ռեկուրսիան:

Ալգորիթմ (կոպիտ ուժ)

  1. Սկսեք արմատից և շարունակեք անցնել երկուական ծառը մինչև արմատ դառնում NULL,
  2. Վերականգեք ձախ և աջ ենթատների բարձրությունը ՝ օգտագործելով բարձրություն () ֆունկցիա
    • Եթե ​​տարբերությունն ավելին է, քան '1':
      • վերադարձ կեղծ. Քանի որ ծառը չի բավարարում հավասարակշռության պայմանը
    • Ռեկուրսիվորեն ստուգեք հավասարակշռության պայմանը ձախ և աջ ենթատեսակների համար
  3. Տպեք արդյունքը

Ալգորիթմ (օպտիմալ)

  1. Եթե ​​ծառը լինի դատարկ, մենք կարող ենք ասել, որ դա հավասարակշռված է: Եթե ​​ոչ, մենք կարող ենք հետևել այլ քայլերի.
  2. Ստեղծեք օգնող գործառույթ ՝ «բարձրություն”Ընթացիկ ենթածառի, օգտագործելով ռեկուրսիա:
  3. Բարձրության գործառույթը կվերադառնա.
    • -1, երբ դա անհավասարակշիռ ծառ է
    • հակառակ դեպքում բարձրությունը:
  4. Այն դեպքում, երբ ենթաընկերություն ունի ձախ կամ աջ ենթատեսակ անհավասարակշիռ, կամ դրանց բարձրությունները տարբերվում են ավելի քան '1' -ով, վերադարձը -1:
  5. Հակառակ դեպքում, վերադարձեք այս ենթատառի բարձրությունը որպես. 1 + առավելագույն (ձախ_բարձրություն, աջ_բարձրություն)

Իրականացման

C ++ րագիր Հավասարակշռված Երկուական ծառի Leetcode լուծման համար

Brute Force մեթոդ

#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

Հավասարակշռված Երկուական ծառի Leetcode լուծման Java ծրագիր

Ամենակոպիտ բռնությունների կիրառումը

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

Երկուական ծառի հավասարակշռված լեոդկոդի լուծույթի բարդության վերլուծություն

Timeամանակի բարդություն

Brute Force մեթոդն ունի ժամանակի բարդություն O (N * N), վատագույն դեպքում (շեղված ծառ): Այնուամենայնիվ, օպտիմալ մոտեցումը գործում է ՎՐԱ) ժամանակը, երբ մենք կատարում ենք միայն մեկ փոխանցում:

Տիեզերական բարդություն

O (N) երկու դեպքում էլ, քանի որ ռեկուրսիան օգտագործում է օժանդակ կույտի տարածությունը: