פתרון Leetcode עץ בינארי מאוזן


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית Google מיקרוסופט
מערך

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+ (שמאל_גובה, ימין_גובה)

יישום

תוכנית 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 * N), במקרה הגרוע ביותר (עץ מוטה). עם זאת, הגישה האופטימלית עובדת עַל) הזמן כשאנחנו מבצעים מעבר יחיד בלבד.

מורכבות בחלל

O (N) בשני המקרים, שכן רקורסיה משתמשת במרחב הערימה העזר.