பைனரி மரம் லீட்கோட் தீர்வின் அதிகபட்ச ஆழம்  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் பேஸ்புக் மைக்ரோசாப்ட்
பைனரி மரம் குறியீட்டு பேட்டி நேர்காணல் தயாரிப்பு லீட்கோட் LeetCodeSolutions மறுசுழற்சி மரம் பயணம்

சிக்கல் அறிக்கை  

சிக்கலில் ஒரு பைனரி மரம் கொடுக்கப்பட்டுள்ளது மற்றும் கொடுக்கப்பட்ட மரத்தின் அதிகபட்ச ஆழத்தை நாம் கண்டுபிடிக்க வேண்டும். ஒரு பைனரி மரத்தின் அதிகபட்ச ஆழம் என்பது ரூட் முனையிலிருந்து மிகக் குறைந்த இலை முனை வரை நீண்ட பாதையில் உள்ள முனைகளின் எண்ணிக்கை.

உதாரணமாக

 
  3
 / \
9   20
   /  \		 
  15   7
3

விளக்கம்: மரத்தின் கீழே சிவப்பு நிறத்தில் காட்டப்பட்டுள்ளபடி இரண்டு நீண்ட பாதைகள் உள்ளன.
பைனரி மரம் லீட்கோட் தீர்வின் அதிகபட்ச ஆழம்

Empty Tree

மரம் காலியாக இருப்பதால், ஆழம் 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) ஆகும், இங்கு N என்பது கொடுக்கப்பட்ட மரத்தில் உள்ள மொத்த முனைகளின் எண்ணிக்கை.

விண்வெளி சிக்கலானது 

ஓ (என்):  மிக மோசமான நிலையில், மரம் முற்றிலும் சமநிலையற்றது, எ.கா. ஒவ்வொரு கணுக்கும் இடது குழந்தை முனை அல்லது சரியான குழந்தை முனை மட்டுமே உள்ளது, பின்னர் மறுநிகழ்வு அழைப்பு N முறை (மரத்தின் உயரம்) ஏற்படும். எனவே அழைப்பு அடுக்கின் அதிகபட்ச அளவு O (N) ஆக இருக்கும்.
சிறந்த விஷயத்தில் (மரம் முற்றிலும் சீரானது), மரத்தின் உயரம் log⁡ (N) ஆக இருக்கும். எனவே, இந்த வழக்கில் இட சிக்கலானது O (log⁡ (N) ஆக இருக்கும்.