متوازن بائنري وڻ ليٽ ڪوڊ حل


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Amazon گوگل Microsoft جي
ڪيريو

A بائنري وڻ ڇا اهو متوازن آهي جيڪڏهن وڻ ۾ هر نوڊ جي کاٻي ۽ سا subي سبزيڊ جي اوچائي جو فرق گهڻو ڪري 1. انهي مسئلي ۾ ، اسان هڪ متوازن بائنري وڻ جي چڪاس ڪرڻ وارا آهيون.

متوازن بائنري وڻ ليٽ ڪوڊ حل

مثال

             2
        
          / 
    
        1

      /
 
    4
Not balanced
     1

  /     \

2         3
Balanced

چرچو

اهو سوچڻ جو ارادو آهي ، لاءِ هر بائنري وڻ ۾ جوڙ ، اسان جانچ ڪري سگھون ٿا ته کاٻي ۽ سا subي سبسڪرز گهربل شرط جي پيروي ڪن يا نه. اهو ئي آهي “زبردستي قوت"طريقو.

پر ، جانچڻ لاءِ ته ڇا وڻ متوازن آهي ، اچڻ جا سبب بنيادي طريقي سان بهتر ٿي سگهن ٿا وقت ۽ جڳهه پيچيدگيون.

اسان هڪ طريقي جي پيروي ڪيون ٿا جيئن اسان هڪ مسئلو ۾ حل ڪريون ٿا تري اپ طريقو. چيڪ ڪريو ته ڇا ھڪڙو نوڊ جو ذيلي ذخيرو پاڻ آھي ، متوازن بائنري وڻن(يا نه) ۽ ساڳئي وقت بائنري وڻ جو عروج حاصل ڪيو ، جيڪو عمومي طور استعمال ڪيو ويندو آهي جڙي ٻيهر.

الگورٿم (دماغي طاقت)

  1. روٽ کان شروع ڪريو ۽ بائنري وڻ کي treeهلائيندي تائين تائين پاڙ ٿي سگهي ٿو NULL
  2. استعمال ڪندي کاٻي ۽ سا subي سبزيز جي قد کي واپس وٺو اوچائي () فعل
    • جيڪڏهن فرق وڌيڪ آهي '1':
      • غلط موٽڻ جئين وڻ متوازن حالت کي پورو نٿو ڪري
    • کاٻي ۽ سا subي سبزيٽس کي متوازن طور تي بيلنس جي حالت ڏسو
  3. نتيجو ڇاپيو

الگورٿيم (ڪمال)

  1. جيڪڏھن وڻ آھي خالي، اسان اهو چئي سگھون ٿا ته اهو متوازن آهي. جيڪڏهن نه ، اسان ٻين قدمن تي عمل ڪري سگهون ٿا:
  2. مددگار فنڪشن ٺاھيو “واپس ڪرڻ لاءِاوچائي”هڪ موجوده ذيلي ذخيري جو ، استعمال ڪرڻ واريون استعمال جي.
  3. اوچائي فنڪشن موٽندي:
    • -1 ، جڏھن اھو ھڪڙي غير متوازن وڻ آھي
    • ٻي صورت ۾ اونچائي.
  4. صورت ۾ هڪ سبيريئر ڇڏي ويو آهي سا rightي يا ساtي سبٽيري غير متوازن ، يا انهن جو قد '1' کان وڌيڪ مختلف آهي ، واپسي -1.
  5. ٻي صورت ۾ ، هن ذيلي ذخيري جي قد کي واپس ڏيو: وڌ کان وڌ (1_ کاٻي_ ساightي ، سا_ي_ اونچائي)

تي عملدرآمد

متوازن بائنري وڻ ليوٽ ڪوڊ حل جو پروگرام C ++

بروٽ فورس جو طريقو

#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

متوازن بائنري وڻ ليوٽ ڪوڊ حل جو جاوا پروگرام

زبردستي قوت

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

متوازن بائنري وڻ ليٽ ڪوڊ حل جو پيچيدگي تجزيو

وقت جي پيچيدگي

بروٽ فورس جو طريقو آھي ھڪڙي وقت جي پيچيدگي اي (اين * اين)، بدترين حالت ۾ (جهڪيل وڻ). بهرحال ، بھترين طريقي سان عمل ڪري ٿو اي (اين) وقت جيئن اسان صرف هڪڙو پاس ڪريون ٿا.

خلائي پيچيدگي

اي (ن) ٻنهي صورتن ۾ ، جئين تسلسل سان معاون اسٽيڪ جي جڳهه استعمال ڪندو آهي.