बायनरी ट्री लीटकोड सोल्यूशनची जास्तीत जास्त खोली


अडचण पातळी सोपे
वारंवार विचारले अडोब ऍमेझॉन फेसबुक मायक्रोसॉफ्ट
बायनरी ट्री पुनरावृत्ती ट्री ट्रॅव्हर्सल

समस्या विधान

समस्येमध्ये ए बायनरी ट्री दिले आहे आणि दिलेल्या झाडाची जास्तीत जास्त खोली शोधून काढावी लागेल. मुळ नोडपासून आतापर्यंतच्या पानाच्या नोडपर्यंतच्या सर्वात लांब मार्गावर असलेल्या नोड्सची संख्या बायनरीच्या झाडाची जास्तीत जास्त खोली असते.

उदाहरण

 
  3
 / \
9   20
   /  \		 
  15   7
3

स्पष्टीकरणः लाल रंगात झाडाच्या खाली दर्शविल्याप्रमाणे दोन सर्वात लांब मार्ग आहेत.
बायनरी ट्री लीटकोड सोल्यूशनची जास्तीत जास्त खोली

Empty Tree
0

झाड रिक्त असल्याने खोली 0 आहे.

0
1

फक्त एकच नोड असल्याने खोली 1 आहे.

दृष्टीकोन

झाडाची जास्तीत जास्त खोली शोधण्यासाठी आम्ही एक साधा रिकर्सिव पध्दत लागू करू शकतो. जिथे प्रत्येक फंक्शन कॉल एक सबट्री प्रस्तुत करेल ज्यात रूट नोडला 'रूट' म्हणतात. रूट नोडपासून सुरू होणार्‍या रिकर्सिव्ह फंक्शनद्वारे आम्ही झाडाला आडवे करतो.

बेस केस आहे जेव्हा सबट्री रिकामी असते म्हणजेच रूट एनयूएल असते. म्हणून आम्ही 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

बायनरी ट्री लीटकोड सोल्यूशनच्या जास्तीत जास्त खोलीसाठी गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन):  आम्ही प्रत्येक नोडला नक्की एकदा भेट देतो, अशा प्रकारे वेळ जटिलता ओ (एन) आहे, जेथे दिलेल्या झाडाच्या एकूण नोडची संख्या एन आहे.

स्पेस कॉम्प्लेक्सिटी 

ओ (एन):  सर्वात वाईट परिस्थितीत, झाड पूर्णपणे असंतुलित आहे, उदा. प्रत्येक नोडमध्ये फक्त चाइल्ड नोड किंवा फक्त उजवा मुला नोड असतो, तर रिकर्सन कॉल एन वेळा होतो (झाडाची उंची). म्हणून कॉल स्टॅकचे जास्तीत जास्त आकार ओ (एन) असेल.
सर्वोत्तम बाबतीत (झाड पूर्णपणे संतुलित आहे), झाडाची उंची लॉग-एन (एन) असेल. म्हणून, या प्रकरणात स्पेस कॉम्प्लेक्सिटी ओ (लॉग⁡ (एन)) असेल.