မျှမျှတတ Binary Tree Leetcode ဖြေရှင်းချက်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ Google Microsoft က
အခင်းအကျင်း

A ဒွိသစ်ပင် သစ်ပင်ရှိ node တိုင်း၏ဘယ်ဘက်နှင့်ညာဖက် subtree တို့၏အမြင့်သည်အမြင့်ဆုံးဖြစ်ပါကအမြင့်ဆုံးဖြစ်သည်။

မျှမျှတတ Binary Tree Leetcode ဖြေရှင်းချက်

နမူနာ

             2
        
          / 
    
        1

      /
 
    4
Not balanced
     1

  /     \

2         3
Balanced

ချဉ်းကပ်နည်း

ဒါဟာစဉ်းစားရန်အလိုလိုသိသည် တိုင်း binary tree ရှိ node ကိုကျွန်ုပ်တို့ဘယ်ဘက်နှင့်ညာ subtrees များသည်လိုအပ်သောအခြေအနေကိုလိုက်နာခြင်းရှိမရှိစစ်ဆေးနိုင်သည်။ ဒါက "Brute အင်အားစု"နည်းလမ်း။

သို့သော်သစ်ပင်၏မျှတမှုရှိ၊ မရှိကိုစစ်ဆေးရန်ချဉ်းကပ်မှုအား အခြေခံ၍ တိုးတက်ကောင်းမွန်အောင်ပြုလုပ်နိုင်သည် အချိန်နှင့်အာကာသ ရှုပ်ထွေးသော။

ကျွန်ုပ်တို့သည်ပြproblemနာကိုဖြေရှင်းနိုင်မည့်ချဉ်းကပ်နည်းကိုလိုက်နာသည် အောက်ခြေ-Up ကို ထုံးစံ။ node တစ်ခု၏ subtrees သည်သူကိုယ်တိုင်၊ မျှတသော binary ဟုတ်မဟုတ်စစ်ဆေးပါ သစ်ပင်များ(ဒါမှမဟုတ်မဟုတ်ပါ) နှင့် recursion သုံးပြီးယေဘူယျနိုင်သည့်တစ်ချိန်တည်းမှာ binary သစ်ပင်၏အမြင့်ရယူပါ။

Algorithm (Brute Force)

  1. အမြစ်မှ စတင်၍ binary သစ်ပင်ကိုတိုင်အောင်မှီဝဲသွားသည် အမြစ် ဖြစ်လာ null
  2. အသုံးပြုပြီးဘယ်နှင့်ညာ subtrees ၏အမြင့်ကိုရယူပါ အမြင့် () function ကို
    • ခြားနားချက်ထက်ပိုလျှင် '1':
      • return false ။ သစ်ပင်ချိန်ခွင်လျှာအခွအေနေကျေနပ်မထားဘူးအဖြစ်
    • ဘယ်ဘက်နှင့်ညာ subtrees များအတွက်ချိန်ခွင်လျှာကိုစစ်ဆေးပါ
  3. ရလဒ်ပုံနှိပ်ပါ

Algorithm (အကောင်းဆုံး)

  1. သစ်ပင်ဖြစ်လျှင် အချည်းနှီးသောမျှမျှတတရှိတယ်လို့ငါတို့ပြောနိုင်တယ်။ မရရှိလျှင်ကျွန်ုပ်တို့သည်အခြားအဆင့်များကိုလိုက်နာနိုင်သည်။
  2. “ ပြန်လာရန်ကူညီမယ့်သူကိုဖန်တီးပါ။အမြင့်recursion သုံးပြီးလက်ရှိ subtree ၏ "။
  3. အမြင့် function ကိုပြန်လာလိမ့်မည်
    • -1 မညီမျှသောအပင်ဖြစ်သည့်အခါ -XNUMX
    • မဟုတ်ရင်အမြင့်။
  4. ကိစ္စရပ်မှာ subtree တစ်ခုက left ဒါမှမဟုတ် right ထွက်သွားတယ် သည်ညီမျှမှု, သို့မဟုတ်သူတို့၏အမြင့်သည် '1' ထက် ပို၍ ကွာခြားပြီး -1 ကိုပြန်သွားပါ။
  5. ဒီလိုမှမဟုတ်ရင်၊ ဒီ subtree ၏အမြင့်ကိုအောက်ပါအတိုင်းပြန်ပို့ပါ။ ၁ + max (ဘယ်သန်၊ ညာ၊ အမြင့်)

အကောင်အထည်ဖော်ရေး

ဟန်ချက်ညီသော Binary Tree Leetcode Solution ၏ C ++ အစီအစဉ်

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

ဟန်ချက်ညီသော Binary Tree Leetcode Solution ၏ Java Program

Brute အင်အားစု

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

Balanced Binary Tree Leetcode Solution ၏ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

Brute Force နည်းလမ်းတွင်အချိန်ရှုပ်ထွေးမှုရှိသည် အို (N * N), အဆိုးဆုံးအမှု၌ (skewed သစ်ပင်) ၌တည်၏။ သို့သော်အကောင်းဆုံးချဉ်းကပ်မှုအတွက်အလုပ်လုပ်တယ် အို (N) ငါတို့သာတစ်ခုတည်း pass ပြုသကဲ့သို့အချိန်။

အာကာသရှုပ်ထွေးမှု

ဖြစ်ရပ်နှစ်ခုလုံးတွင်အို (N) သည်ပြန်လည်လုပ်ဆောင်ခြင်းသည်အရန်နေရာ stack space ကိုအသုံးပြုသည်။