বাইনারি ট্রি লেটকোড সমাধানের সর্বোচ্চ গভীরতা


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক ফেসবুক মাইক্রোসফট
বাইনারি ট্রি recursion ট্রি ট্রভারসাল

সমস্যা বিবৃতি

সমস্যায় ক বাইনারি গাছ দেওয়া হয়েছে এবং প্রদত্ত গাছের সর্বাধিক গভীরতা আমাদের খুঁজে বের করতে হবে। বাইনারি গাছের সর্বাধিক গভীরতা হ'ল মূল নোড থেকে নীচের পাতার নোড পর্যন্ত দীর্ঘতম পথ বরাবর নোডের সংখ্যা।

উদাহরণ

 
  3
 / \
9   20
   /  \		 
  15   7
3

ব্যাখ্যা: লাল বর্ণের নীচে গাছের মতো দুটি দীর্ঘতম পথ সম্ভব।
বাইনারি ট্রি লেটকোড সমাধানের সর্বোচ্চ গভীরতা

Empty Tree
0

গাছ খালি থাকায় গভীরতা 0 হয়।

0
1

যেহেতু কেবল একটি নোড রয়েছে, গভীরতা 1।

অভিগমন

গাছের সর্বাধিক গভীরতা সন্ধান করতে আমরা একটি সাধারণ পুনরাবৃত্ত পদ্ধতির প্রয়োগ করতে পারি। যেখানে প্রতিটি ফাংশন কল এমন একটি সাবট্রির প্রতিনিধিত্ব করবে যার রুট নোডকে 'রুট' হিসাবে ডাকা হয়। আমরা রুট নোড থেকে শুরু করে পুনরাবৃত্ত ফাংশন দ্বারা গাছটি অতিক্রম করি।

সুতরাং বেস কেসটি যখন সাবট্রিটি খালি থাকে তবে মূলটি NUL হয়। সুতরাং আমরা 0 হিসাবে গভীরতা ফিরে।

মূলটি যদি নুল না হয় তবে একই বামটি তার বাম শিশু এবং ডান সন্তানের জন্য পুনরাবৃত্তভাবে কল করুন।

চিত্র হিসাবে দেখানো হয়েছে, যখন দুটি সন্তানের ফাংশন তার গভীরতা ফিরিয়ে দেয় আমরা এই দুটি সাবট্রির মধ্যে সর্বাধিক বাছাই করি এবং এর সাথে 1 যুক্ত করার পরে এই মানটি ফেরত দেব (বর্তমান নোড যা দুটি সাবট্রির পিতা বা মাতা হয়) যোগ করব।

বাইনারি গাছের সর্বোচ্চ গভীরতা

বাস্তবায়ন

বাইনারি ট্রি লেটকোড সমাধানের সর্বোচ্চ গভীরতার জন্য সি ++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

int maxDepth(TreeNode* root) 
{
    if(root==NULL) return 0;
    return 1+max(maxDepth(root->left),maxDepth(root->right));
}

int main() 
{
    TreeNode *root= new TreeNode(3);
    root->left= new TreeNode(9);
    root->right= new TreeNode(20);
    root->right->left= new TreeNode(15);
    root->right->right= new TreeNode(7);
    
    cout<<maxDepth(root)<<endl; 
  return 0; 
}
3

বাইনারি ট্রি লেটকোড সমাধানের সর্বোচ্চ গভীরতার জন্য জাভা প্রোগ্রাম

import java.util.*;
import java.lang.*;
class TreeNode 
{
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) 
      {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

class MaxDepth
{  
    public static int maxDepth(TreeNode root) 
    {
        if(root==null) return 0;
        
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
    
    public static void main(String args[])
    {
        TreeNode root= new TreeNode(3);
        root.left= new TreeNode(9);
        root.right= new TreeNode(20);
        root.right.left= new TreeNode(15);
        root.right.right= new TreeNode(7);
       
        System.out.println(maxDepth(root));
        
    }
}
3

বাইনারি ট্রি লেটকোড সমাধানের সর্বোচ্চ গভীরতার জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু) :  আমরা প্রতিটি নোড ঠিক একবার দেখতে যাই, সুতরাং সময় জটিলতা হ'ল (এন), যেখানে প্রদত্ত গাছে নোডের মোট সংখ্যা এন।

স্পেস জটিলতা ity 

চালু) :  সবচেয়ে খারাপ ক্ষেত্রে, গাছটি সম্পূর্ণ ভারসাম্যহীন, যেমন প্রতিটি নোডে কেবলমাত্র শিশু নোড বা কেবল ডান চাইল্ড নোড থাকে, তবে পুনরাবৃত্তি কলটি N বার (গাছের উচ্চতা) প্রদর্শিত হবে occur সুতরাং কল স্ট্যাকের সর্বাধিক আকার হ'ল ও (এন)।
সর্বোত্তম ক্ষেত্রে (গাছ সম্পূর্ণ সুষম হয়), গাছের উচ্চতা লগ (এন) হবে। সুতরাং, এই ক্ষেত্রে স্পেস জটিলতা হ'ল O (লগ (এন))।