ການແກ້ໄຂບັນຫາແບບ Leetcode Binary ທີ່ສົມດຸນ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon ກູໂກ Microsoft
Array

A ຕົ້ນໄມ້ຖານສອງ ແມ່ນລະດັບຄວາມສູງຖ້າຄວາມແຕກຕ່າງຂອງລະດັບຄວາມສູງຂອງ ລຳ ດັບຊ້າຍແລະຂວາຂອງທຸກໆຂໍ້ໃນຕົ້ນໄມ້ແມ່ນມີຫຼາຍທີ່ສຸດ 1. ໃນບັນຫານີ້, ພວກເຮົາຈະກວດເບິ່ງຕົ້ນໄມ້ໄບນາລີທີ່ສົມດຸນ.

ການແກ້ໄຂບັນຫາແບບ Leetcode Binary ທີ່ສົມດຸນ

ຍົກຕົວຢ່າງ

             2
        
          / 
    
        1

      /
 
    4
Not balanced
     1

  /     \

2         3
Balanced

ວິທີການ

ມັນເປັນສິ່ງທີ່ມີຄວາມຮູ້ສຶກຢາກຮູ້ວ່າ, ສຳ ລັບ ທຸກ node ຢູ່ໃນຕົ້ນໄມ້ຖານສອງ, ພວກເຮົາສາມາດກວດເບິ່ງໄດ້ວ່າເຄື່ອງ ໝາຍ ເລກເບື້ອງຊ້າຍແລະຂວາ ດຳ ເນີນຕາມເງື່ອນໄຂທີ່ຕ້ອງການ. ນັ້ນແມ່ນ "ຜົນບັງຄັບໃຊ້ສັດ” ວິທີການ.

ແຕ່ວ່າ, ເພື່ອກວດກາເບິ່ງວ່າຕົ້ນໄມ້ມີຄວາມສົມດຸນ, ວິທີການດັ່ງກ່າວສາມາດປັບປຸງໄດ້ແນວໃດ ເວລາແລະອະວະກາດ ຄວາມສັບສົນ.

ພວກເຮົາປະຕິບັດຕາມວິທີການດັ່ງກ່າວທີ່ພວກເຮົາແກ້ໄຂບັນຫາໃນ ລຸ່ມ Up ລັກສະນະ. ກວດເບິ່ງວ່າອະນຸພາກຂອງ node ແມ່ນຕົວຂອງມັນເອງ, ຄູ່ຖານສອງທີ່ສົມດຸນ ຕົ້ນໄມ້(ຫຼື​ບໍ່) ແລະໄດ້ຮັບຄວາມສູງຂອງຕົ້ນໄມ້ໄບນາລີໃນເວລາດຽວກັນ, ເຊິ່ງສາມາດເຮັດໄດ້ໂດຍທົ່ວໄປໂດຍໃຊ້ການເອີ້ນຄືນ.

ສູດການຄິດໄລ່ (ກຳ ລັງແຮງງານ)

  1. ເລີ່ມຕົ້ນຈາກຮາກແລະສືບຕໍ່ຜ່ານຕົ້ນໄມ້ຖານສອງຈົນກ່ວາ ຮາກ ກາຍເປັນ NULL
  2. ດຶງລະດັບຄວາມສູງຂອງລັດຖະມົນຕີຊ້າຍແລະຂວາໂດຍໃຊ້ ລວງສູງ () ຫນ້າທີ່
    • ຖ້າຄວາມແຕກຕ່າງແມ່ນຫຼາຍກ່ວາ '1':
      • ກັບຄືນບໍ່ຖືກຕ້ອງ. ເປັນຕົ້ນໄມ້ບໍ່ພໍໃຈກັບສະພາບການດຸ່ນດ່ຽງ
    • ກວດເບິ່ງສະພາບການດຸ່ນດ່ຽງ ສຳ ລັບບົດບັນຍັດຊ້າຍແລະຂວາຄືນ
  3. ພິມຜົນໄດ້ຮັບ

ສູດການຄິດໄລ່ (ດີທີ່ສຸດ)

  1. ຖ້າຕົ້ນໄມ້ ຫວ່າງເປົ່າ, ພວກເຮົາສາມາດເວົ້າໄດ້ວ່າມັນມີຄວາມສົມດຸນ. ຖ້າບໍ່, ພວກເຮົາສາມາດປະຕິບັດຕາມຂັ້ນຕອນອື່ນໆ:
  2. ສ້າງ ໜ້າ ທີ່ຜູ້ຊ່ວຍເພື່ອກັບຄືນ“ລະດັບຄວາມສູງ” ຂອງລັດຖະບັນຍັດໃນປະຈຸບັນ, ໂດຍ ນຳ ໃຊ້ການເອີ້ນຄືນ.
  3. Height Function ຈະກັບຄືນ:
    • -1, ໃນເວລາທີ່ມັນເປັນຕົ້ນໄມ້ທີ່ບໍ່ສົມດຸນ
    • ລະດັບຄວາມສູງຖ້າບໍ່ດັ່ງນັ້ນ.
  4. ໃນກໍລະນີມີລັດຖະບັນຍັດມີຊ້າຍຫຼືຊ້າຍ ບໍ່ສົມດຸນ, ຫຼືຄວາມສູງຂອງພວກມັນແຕກຕ່າງກັນຫຼາຍກວ່າ '1', ກັບຄືນ -1.
  5. ຖ້າບໍ່ດັ່ງນັ້ນ, ໃຫ້ກັບຄືນຄວາມສູງຂອງ ດຳ ລັດສະບັບນີ້ເປັນ: 1 + ສູງສຸດ (ເບື້ອງຊ້າຍ, ເບື້ອງຂວາແລະຈຸດ)

ການປະຕິບັດ

ໂຄງການ 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

Java Program ຂອງການແກ້ໄຂບັນຫາຕົ້ນໄມ້ທີ່ສົມເຫດສົມຜົນ 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 Solution ທີ່ສົມດຸນເປັນໄມ້ຢືນຕົ້ນ

ຄວາມສັບສົນເວລາ

ວິທີການ Brute Force ມີຄວາມສັບສົນເວລາ O (N * N), ໃນກໍລະນີທີ່ບໍ່ດີທີ່ສຸດ (ຕົ້ນໄມ້ທີ່ບໍ່ຄ່ອຍເຊື່ອງ່າຍໆ). ຢ່າງໃດກໍ່ຕາມ, ວິທີການທີ່ດີທີ່ສຸດເຮັດວຽກຢູ່ໃນ ໂອ (N) ທີ່ໃຊ້ເວລາດັ່ງທີ່ພວກເຮົາເຮັດຜ່ານດຽວເທົ່ານັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

O (N) ໃນທັງສອງກໍລະນີ, ຍ້ອນວ່າການເອີ້ນຄືນໃຊ້ຊ່ອງ stack stack ຊ່ວຍ.