بائنری ٹری لیٹ کوڈ حل کی زیادہ سے زیادہ گہرائی


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایڈوب ایمیزون فیس بک مائیکروسافٹ
ثنائی درخت تکرار درخت ٹراورسال

مسئلہ یہ بیان

مسئلے میں a بائنری ٹری دی گئی ہے اور ہمیں دیئے گئے درخت کی زیادہ سے زیادہ گہرائی معلوم کرنا ہوگی۔ بائنری کے درخت کی زیادہ سے زیادہ گہرائی جڑ نوڈ سے لے کر دور تک پتی کے نوڈ تک لمبی لمبی راہ کے ساتھ نوڈس کی تعداد ہے۔

مثال کے طور پر

 
  3
 / \
9   20
   /  \		 
  15   7
3

وضاحت: دو لمبے لمبے راستے ہیں جیسے درخت کے نیچے سرخ رنگ میں دکھایا گیا ہے۔
بائنری ٹری لیٹ کوڈ حل کی زیادہ سے زیادہ گہرائی

Empty Tree
0

چونکہ درخت خالی ہے ، گہرائی 0 ہے۔

0
1

چونکہ وہاں صرف ایک نوڈ ہے ، گہرائی 1 ہے۔

نقطہ نظر

درخت کی زیادہ سے زیادہ گہرائی کا پتہ لگانے کے لئے ہم ایک سادہ تکرار نقطہ نظر استعمال کرسکتے ہیں۔ جہاں ہر فنکشن کال ایک سب ٹری کی نمائندگی کرے گی جس میں جڑ نوڈ ہوتا ہے جسے 'روٹ' کہا جاتا ہے۔ ہم جڑ کے نوڈ سے شروع ہونے والی ایک بار بار چلنے والی تقریب کے ذریعہ درخت کو عبور کرتے ہیں۔

تو بیس کیس اس وقت ہوتا ہے جب سب ٹری خالی ہو یعنی جڑ NULL ہو۔ لہذا ہم 0 کی طرح گہرائی میں واپس آتے ہیں۔

اگر جڑ NULL نہیں ہے تو ، اسی فنکشن کو اس کے بائیں اور دائیں بچے کے لئے متواتر کال کریں۔

جیسا کہ اعداد و شمار میں دکھایا گیا ہے ، جب دونوں بچوں کے فنکشن اس کی گہرائی کو لوٹاتے ہیں تو ہم ان دونوں ذیلی ذخیروں میں سے زیادہ سے زیادہ کو منتخب کرتے ہیں اور اس میں 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

ثنائی درخت لیٹ کوڈ حل کی زیادہ سے زیادہ گہرائی کے لئے پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N):  ہم ہر نوڈ کو عین ایک بار ملاحظہ کرتے ہیں ، اس طرح وقت کی پیچیدگی O (N) ہوتی ہے ، جہاں دیئے گئے درخت میں N (نوڈس) کی کل تعداد ہوتی ہے۔

خلائی پیچیدگی 

O (N):  بدترین صورتحال میں ، درخت مکمل طور پر متوازن ہے ، جیسے کہ ہر نوڈ میں صرف بچہ کا نوڈ رہ جاتا ہے یا صرف دائیں بچہ کا نوڈ ہوتا ہے ، پھر تکرار کال N وقت (درخت کی اونچائی) پر واقع ہوگی۔ لہذا کال اسٹیک کی زیادہ سے زیادہ سائز O (N) ہوگی۔
بہترین صورت میں (درخت مکمل طور پر متوازن ہے) ، درخت کی اونچائی لاگ (N) ہوگی۔ لہذا ، اس معاملے میں خلائی پیچیدگی O (log⁡ (N)) ہوگی۔