โซลูชัน Leetcode ต้นไม้ไบนารีที่สมดุล


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน Google ไมโครซอฟท์
แถว

A ต้นไม้ไบนารี คือความสูงที่สมดุลถ้าความแตกต่างของความสูงของทรีย่อยด้านซ้ายและด้านขวาของทุกโหนดในทรีมีค่ามากที่สุด 1 ในปัญหานี้เราจะตรวจสอบต้นไม้ไบนารีที่สมดุล

โซลูชัน Leetcode ต้นไม้ไบนารีที่สมดุล

ตัวอย่าง

             2
        
          / 
    
        1

      /
 
    4
Not balanced
     1

  /     \

2         3
Balanced

เข้าใกล้

มันเป็นเรื่องง่ายที่จะคิดว่าสำหรับ ทุกๆ โหนดในต้นไม้ไบนารีเราสามารถตรวจสอบว่าต้นไม้ย่อยซ้ายและขวาเป็นไปตามเงื่อนไขที่กำหนดหรือไม่ เป็นเรื่องที่ "โหดเหี้ยม" วิธี.

แต่เพื่อตรวจสอบว่าต้นไม้มีความสมดุลหรือไม่สามารถปรับปรุงแนวทางได้โดยอาศัยเหตุผล เวลาและอวกาศ ความซับซ้อน

เราปฏิบัติตามแนวทางที่เราแก้ปัญหาในรูปแบบ จากล่างขึ้นบน ลักษณะ. ตรวจสอบว่าต้นไม้ย่อยของโหนดนั้นเป็นไบนารีที่สมดุลหรือไม่ ต้นไม้(หรือไม่) และรับความสูงของต้นไม้ไบนารีในเวลาเดียวกันซึ่งสามารถสรุปได้โดยใช้การเรียกซ้ำ

อัลกอริทึม (Brute Force)

  1. เริ่มต้นจากรากและข้ามต้นไม้ไบนารีไปเรื่อย ๆ จนถึง ราก จะกลายเป็น NULL
  2. ดึงความสูงของต้นไม้ย่อยซ้ายและขวาโดยใช้ ความสูง () ฟังก์ชัน
    • ถ้าความแตกต่างมากกว่า '1':
      • กลับเท็จ เนื่องจากต้นไม้ไม่เป็นไปตามสภาพสมดุล
    • ตรวจสอบสภาพความสมดุลของต้นไม้ย่อยซ้ายและขวาแบบวนซ้ำ
  3. พิมพ์ผลลัพธ์

อัลกอริทึม (ที่เหมาะสมที่สุด)

  1. ถ้าเป็นต้นไม้ ไม่มีข้อมูลเราสามารถพูดได้ว่ามันสมดุล หากไม่เป็นเช่นนั้นเราสามารถทำตามขั้นตอนอื่น ๆ ได้:
  2. สร้างฟังก์ชันตัวช่วยเพื่อส่งกลับ“ความสูง” ของแผนผังย่อยปัจจุบันโดยใช้การเรียกซ้ำ
  3. ฟังก์ชันความสูงจะกลับมา:
    • -1 เมื่อมันเป็นต้นไม้ที่ไม่สมดุล
    • ความสูงเป็นอย่างอื่น
  4. ในกรณีที่ทรีย่อยมีทรีย่อยซ้ายหรือขวา ไม่สมดุล หรือความสูงต่างกันมากกว่า '1' ให้ส่งกลับ -1
  5. มิฉะนั้นให้คืนค่าความสูงของทรีย่อยนี้เป็น: 1 + สูงสุด (left_height, right_height)

การดำเนินงาน

โปรแกรม C ++ ของ Balanced Binary Tree Leetcode Solution

วิธี 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 ของ Balanced Binary Tree Leetcode Solution

โหดเหี้ยม

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 ทรีไบนารีที่สมดุล

ความซับซ้อนของเวลา

วิธี Brute Force มีความซับซ้อนของเวลา O (N * N)ในกรณีที่เลวร้ายที่สุด (ต้นไม้เอียง) อย่างไรก็ตามแนวทางที่ดีที่สุดใช้ได้ผลใน บน) เวลาที่เราทำเพียงครั้งเดียวเท่านั้น

ความซับซ้อนของอวกาศ

O (N) ในทั้งสองกรณีเนื่องจากการเรียกซ้ำใช้พื้นที่สแต็กเสริม