حداقل عمق محلول کد باینری درخت  


سطح دشواری ساده
اغلب در آمازون سیب فیس بوک
الگوریتم درخت باینری عرض اول جستجو برنامه نویسی عمق جستجو اول مصاحبه مصاحبه آماده LeetCode LeetCodeSolutions

در این مشکل ، باید طول کوتاهترین مسیر را از ریشه تا هر برگ موجود در آن پیدا کنیم درخت دودویی. توجه داشته باشید که "طول مسیر" در اینجا به معنای تعداد گره ها از گره ریشه تا گره برگ است. به این طول حداقل عمق درخت دوتایی گفته می شود.

مثال  

ورودی

حداقل عمق محلول کد باینری درختسنجاق

 

 

 

 

 

 

 

2

توضیح

کوتاهترین مسیر این است: 2 -> 1 ، که طول 2 است

ورودی

 

 

 

 

 

 

 

3

توضیح

کوتاهترین مسیر این است: 1 -> 2 -> 3، به طول 3

رویکرد (بازگشتی)  

این مشکل از نظر ساختاری مشابه یافتن ارتفاع یک درخت باینری است اما در این حالت ، ما باید حداقل ارتفاع / عمق را بین ریشه و هر برگ درخت پیدا کنیم. ما می توانیم با استفاده از حداقل عمق زیر شاخه های چپ و راست ریشه را بازیابی کنیم عمق جستجو اول (DFS) و سپس حداقل دو عمق را برگردانید. بعضی از موارد را باید در نظر بگیریم که یکی از شاخه های چپ و راست یک گره باشد NULL. اگر زیر درخت چپ باشد خالی، ارتفاعی برابر با برمی گرداند اما همانطور که در این زیر درخت هیچ برگی پیدا نکردیم ، بنابراین این پاسخ اشتباهی خواهد بود از این رو ، ما فقط زمانی که گره فراخوانی شده است لازم است که تابع بازگشتی را فراخوانی کنیم نه خالی.

همچنین مشاهده کنید
راه حل کدگذاری Pascal's Triangle II

الگوریتم

  1. ایجاد یک تابع minDepth () برای بازگرداندن حداقل عمق ریشه عبور داده شده
  2. اگر ریشه باشد NULL، برگشت
  3. در صورت هر دو ترک کرد و راست زیرشاخه ها هستند NULL، بازگشت 1
  4. اگر زیر درخت چپ باشد NULL، برگشت 1 + دقیقه عمق (ریشه -> راست)
  5. در غیر این صورت ، درخت فرعی مناسب است NULL، برگشت 1 + دقیقه عمق (ریشه -> چپ)
  6. بازگشت 1+ حداقل (عمق دقیقه(ریشه> چپ) ، عمق دقیقه(root-> right))

اجرای حداقل عمق محلول کد باینری درخت

برنامه 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 minDepth(treeNode* root)
{
    if(root == NULL)
        return 0;
    if(root->left == NULL && root->right == NULL)
        return 1;
    if(root->left == NULL)
        return 1 + minDepth(root->right);
    if(root->right == NULL)
        return 1 + minDepth(root->left);
    return 1 + min(minDepth(root->left) , minDepth(root->right));
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->right->left = new treeNode(4);
    root->right->right = new treeNode(5);
    cout << minDepth(root) << '\n';
}

برنامه جاوا

import java.util.*;

class treeNode
{
    int value;
    treeNode left, right;
    public treeNode(int x)
    {
        value = x;
        left = right = null;
    }
}

class Pair
{
    treeNode key;
    int value;

    Pair(treeNode root , int val)
    {
        key = root;
        value = val;
    }
}

class Minimum_Depth_Of_A_Binary_Tree
{
    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(3);
        root.right.left = new treeNode(4);
        root.right.right = new treeNode(5);
        System.out.println(minDepth(root));
    }

    static int minDepth(treeNode root)
    {
        if(root == null)
            return 0;
        if(root.left == null && root.right == null)
            return 1;
        if(root.left == null)
            return 1 + minDepth(root.right);
        if(root.right == null)
            return 1 + minDepth(root.left);
        return 1 + Math.min(minDepth(root.left) , minDepth(root.right));

    }
}
2

تجزیه و تحلیل پیچیدگی حداقل عمق محلول کد دودویی درخت باینری

پیچیدگی زمان

بر)، همانطور که حتی در بدترین حالت یکبار کل درخت را پیمایش می کنیم.

پیچیدگی فضا

بر). هنگامی که درخت باینری کج می شود ، قاب های پشته بازگشتی ممکن است تا فضای O (N) مصرف کنند.

همچنین مشاهده کنید
رشته ای را با کاراکترهایی که تعداد عجیب و غریب دارند راه حل کد ایجاد کنید

رویکرد (تکراری)  

ما می توانید استفاده کنید جستجو برای اولین بار (BFS) برای پیدا کردن اولین گره که یک برگ است و بازگشت عمق آن از ریشه. می توانیم از یک صف برای ذخیره یک جفت گره و عمق آنها از گره ریشه استفاده کنیم. همانطور که گره ای را دریافت می کنیم که یک برگ است ، عمق آن را برمی گردانیم.

الگوریتم

  1. اگر ریشه است NULL، برگشت
  2. یک صف از جفت گره های درخت و اعداد صحیح را شروع کنید
  3. گره ریشه را با عمق آن به صف فشار دهید 1
  4. در حالی که صف خالی نیست:
    • عمق و آدرس گره عنصر صف جلو را بازیابی کنید
    • یک مورد را از صف خارج کنید
    • اگر گره جلو باشد NULL، عمق آن را برگردانید
    • فشار دهید ترک کرد و راست گره های درخت وجود دارد نه تهی
  5. برگشت -1 برای حفظ نحو برنامه همانطور که تابع یک عدد صحیح را برمی گرداند

اجرای حداقل عمق محلول کد باینری درخت

برنامه 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 minDepth(treeNode* root)
{
    if(root == NULL)
        return 0;
    queue < pair <treeNode* , int> > q;
    q.push({root , 1});

    treeNode* frontNode;
    int depth;

    while(!q.empty())
    {
        frontNode = q.front().first;
        depth = q.front().second;
        q.pop();

        if(frontNode->left == NULL && frontNode->right == NULL)
            return depth;

        if(frontNode->left != NULL)
            q.push({frontNode->left , depth + 1});

        if(frontNode->right != NULL)
            q.push({frontNode->right , depth + 1});
    }
    return -1;
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->right->left = new treeNode(4);
    root->right->right = new treeNode(5);
    cout << minDepth(root) << '\n';
}


برنامه جاوا

import java.util.*;

class treeNode
{
    int value;
    treeNode left, right;
    public treeNode(int x)
    {
        value = x;
        left = right = null;
    }
}

class Pair
{
    treeNode key;
    int value;

    Pair(treeNode root , int val)
    {
        key = root;
        value = val;
    }
}

class Minimum_Depth_Of_A_Binary_Tree
{
    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(3);
        root.right.left = new treeNode(4);
        root.right.right = new treeNode(5);
        System.out.println(minDepth(root));
    }

    static int minDepth(treeNode root)
    {
        if(root == null)
            return 0;
        LinkedList <Pair> q = new LinkedList<>();
        q.add(new Pair(root , 1));

        treeNode frontNode;
        int depth;

        while(q.size() > 0)
        {
            frontNode = q.peek().key;
            depth = q.peek().value;

            q.remove();

            if(frontNode.left == null && frontNode.right == null)
                return depth;

            if(frontNode.left != null)
                q.add(new Pair(frontNode.left , depth + 1));

            if(frontNode.right != null)
                q.add(new Pair(frontNode.right , depth + 1));
        }
        return -1;
    }
}
2

تجزیه و تحلیل پیچیدگی حداقل عمق محلول کد دودویی درخت باینری

پیچیدگی زمان

بر)، همانطور که یکبار دیگر کل درخت را پیمایش می کنیم.

همچنین مشاهده کنید
قیمت های نهایی با تخفیف ویژه در فروشگاه راه حل کد

پیچیدگی فضا

بر)، همانطور که برای ذخیره جزئیات هر گره از یک صف استفاده می کنیم.