बाइनरी ट्री लेटकोड समाधानको अधिकतम गहराई


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब अमेजन फेसबुक माइक्रोसफ्ट
बाइनरी रूख पुनरावृत्ति रूख ट्राभर्सल

समस्या वक्तव्य

समस्यामा बाइनरी रूख दिइएको छ र हामीले दिएको रूखको अधिकतम गहिराइ पत्ता लगाउनु पर्छ। बाइनरी रूखको अधिकतम गहिराई भनेको जरा नोडदेखि टाढा टाढा पत्ती नोड सम्म सबैभन्दा लामो पथ सहित नोडहरूको संख्या हो।

उदाहरणका

 
  3
 / \
9   20
   /  \		 
  15   7
3

स्पष्टीकरण: त्यहाँ दुई सम्भव सबैभन्दा लामो मार्गहरू छन् जुन रातो रंगमा रूखको मुनि देखाइएको छ।
बाइनरी ट्री लेटकोड समाधानको अधिकतम गहराई

Empty Tree
0

रूख खाली भएकोले, गहिराई ० छ।

0
1

त्यहाँ केवल एक नोड भएकोले, गहिराई १ हो।

दृष्टिकोण

रूखको अधिकतम गहिराइ पत्ता लगाउन हामी एक साधारण रिकर्सिभ दृष्टिकोण लागू गर्न सक्छौं। जहाँ प्रत्येक प्रकार्य कलले एक सबट्री प्रतिनिधित्व गर्दछ जसमा रूट नोड हुन्छ जसलाई 'रुट' भनेर चिनिन्छ। हामीले रूखलाई नोडबाट शुरू हुने रिकर्सिभ प्रकार्यबाट ट्रान्समा पार्दछौं।

त्यसो भए बेस केस भनेको सबट्री खाली हुँदा रूट NULL हुन्छ। त्यसैले हामी ० को रूपमा गहिराई फिर्ता गर्छौं।

यदि रूट NULL छैन भने, यसको बायाँ बच्चा र दायाँ बच्चाको लागि समान कार्यहरू रिकर्सिभिय कल गर्नुहोस्।

फिगरमा देखाइएझैं जब दुई बच्चा फंक्शनले यसको गहिराई फिर्ता गर्छ भने हामी यी दुई उप-ट्रीहरूमध्येबाट अधिकतम छान्छौं र यसमा १ थप गरे पछि यो मान फर्काउँछौं (हालको नोड जोड्दैछ जुन दुई उप-ट्रीहरूको अभिभावक हो)।

बाइनरी रूखको अधिकतम गहराई

कार्यान्वयन

बाइनरी ट्री लेटकोड समाधानको अधिकतम गहराईको लागि C ++ कार्यक्रम

#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):  सबैभन्दा नराम्रो अवस्थामा, रूख पूर्ण रूपले असंतुलित छ, उदाहरणका लागि प्रत्येक नोडमा केवल बच्चा नोड वा बायाँ चाइल्ड नोड मात्र बाँकी हुन्छ, तब रिकर्सन कल एन पटक (रूखको उचाई) देखा पर्दछ। त्यसैले कल स्ट्याकको अधिकतम आकार ओ (एन) हुनेछ।
उत्तम अवस्थामा (रूख पूर्ण रूपमा सन्तुलित छ), रूखको उचाइ log⁡ (N) हुनेछ। तसर्थ, यस अवस्थामा अन्तरिक्ष जटिलता O (log⁡ (N)) हुनेछ।