બાઈનરી ટ્રી લીટકોડ સોલ્યુશનની મહત્તમ thંડાઈ


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન ફેસબુક માઈક્રોસોફ્ટ
દ્વિસંગી વૃક્ષ રિકર્ઝન વૃક્ષ આડેધડ

સમસ્યા નિવેદન

સમસ્યામાં એ દ્વિસંગી વૃક્ષ આપવામાં આવે છે અને આપેલ વૃક્ષની મહત્તમ depthંડાઈ શોધવા પડશે. દ્વિસંગી ઝાડની મહત્તમ depthંડાઈ એ રુટ નોડથી દૂરના પર્ણ નોડ સુધીના સૌથી લાંબા માર્ગ સાથે ગાંઠોની સંખ્યા છે.

ઉદાહરણ

 
  3
 / \
9   20
   /  \		 
  15   7
3

સમજૂતી: લાલ રંગમાં નીચે વૃક્ષમાં બતાવ્યા પ્રમાણે બે સંભવિત લાંબી રસ્તો છે.
બાઈનરી ટ્રી લીટકોડ સોલ્યુશનની મહત્તમ thંડાઈ

Empty Tree
0

જેમ કે વૃક્ષ ખાલી છે, depthંડાઈ 0 છે.

0
1

ફક્ત એક જ નોડ હોવાથી, depthંડાઈ 1 છે.

અભિગમ

ઝાડની મહત્તમ depthંડાઈ શોધવા માટે અમે એક સરળ રિકર્સીવ અભિગમ લાગુ કરી શકીએ છીએ. જ્યાં દરેક ફંક્શન ક callલ એક સબટ્રીનું પ્રતિનિધિત્વ કરશે જેમાં રુટ નોડ હોય જેને 'રૂટ' તરીકે ઓળખવામાં આવે છે. અમે રુટ નોડથી શરૂ થતા રિકર્સીવ ફંક્શન દ્વારા ઝાડને વટાવીએ છીએ.

તેથી બેઝ કેસ છે જ્યારે સબટ્રી ખાલી હોય એટલે કે રુટ NULL હોય. તેથી આપણે 0 તરીકે depthંડાઈ પરત કરીએ છીએ.

જો રુટ નલ ન હોય તો, તેના ડાબા બાળક અને જમણા બાળક માટે સમાન ફંક્શનને વારંવાર ક callલ કરો.

આકૃતિમાં બતાવ્યા પ્રમાણે, જ્યારે બે બાળકનું કાર્ય તેની depthંડાઈ પરત કરે છે ત્યારે આપણે આ બે પેટાશ્રીમાંથી મહત્તમ પસંદ કરીએ છીએ અને તેમાં 1 ઉમેર્યા પછી આ મૂલ્ય પાછું આપીએ છીએ (વર્તમાન નોડ ઉમેરવાનું કે જે બે સબટ્રીઝનો પિતૃ છે).

દ્વિસંગી વૃક્ષની મહત્તમ Depંડાઈ

અમલીકરણ

બાઈનરી ટ્રી લીટકોડ સોલ્યુશનની મહત્તમ thંડાઈ માટે સી ++ પ્રોગ્રામ

#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

બાઈનરી ટ્રી લીટકોડ સોલ્યુશનની મહત્તમ thંડાઈ માટે જાવા પ્રોગ્રામ

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

બાઈનરી ટ્રી લીટકોડ સોલ્યુશનની મહત્તમ thંડાઈ માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન):  અમે દરેક નોડની બરાબર એક વખત મુલાકાત લઈએ છીએ, આમ સમય જટિલતા O (N) છે, જ્યાં આપેલ વૃક્ષમાં N નોડની કુલ સંખ્યા છે.

અવકાશ જટિલતા 

ઓ (એન):  સૌથી ખરાબ કિસ્સામાં, ઝાડ સંપૂર્ણપણે અસંતુલિત છે, દા.ત. દરેક નોડમાં ફક્ત બાળક નોડ અથવા ફક્ત જમણો ચાઇલ્ડ નોડ હોય છે, પછી પુનરાવર્તન કursલ એન ટાઇમ્સ (ઝાડની heightંચાઇ) પર આવે છે. તેથી ક callલ સ્ટેકનું મહત્તમ કદ O (N) હશે.
શ્રેષ્ઠ કિસ્સામાં (વૃક્ષ સંપૂર્ણપણે સંતુલિત છે), ઝાડની .ંચાઈ લોગ⁡ (એન) હશે. તેથી, આ કિસ્સામાં જગ્યાની જટિલતા ઓ (લોગ (એન)) હશે.