የሁለትዮሽ ዛፍ Leetcode መፍትሄ ከፍተኛ ጥልቀት  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን ፌስቡክ የ Microsoft
ስልተ ሁለትዮሽ ዛፍ ምስጠራ ቃለ መጠይቅ interviewprep ሊት ኮድ LeetCodeSolutions ዳግም መጥፋት የዛፍ ተሻጋሪ

የችግሩ መግለጫ  

በችግሩ ውስጥ ሀ ሁለትዮሽ ዛፍ ተሰጥቷል እናም የተሰጠውን ዛፍ ከፍተኛ ጥልቀት ማወቅ አለብን ፡፡ የሁለትዮሽ ዛፍ ከፍተኛ ጥልቀት ከስር መስቀለኛ መንገድ እስከ በጣም ርቆ ወደ ቅጠል መስቀለኛ መንገድ ድረስ ባለው ረጅሙ መንገድ ላይ የአንጓዎች ብዛት ነው።

ለምሳሌ

 
  3
 / \
9   20
   /  \		 
  15   7
3

ማብራሪያ በቀይ ቀለም ከዛፉ በታች እንደሚታየው ሁለት ሊሆኑ የሚችሉ ረጅሙ መንገዶች አሉ ፡፡
የሁለትዮሽ ዛፍ Leetcode መፍትሄ ከፍተኛ ጥልቀት

Empty Tree

ዛፉ ባዶ ስለሆነ ጥልቀት 0 ነው ፡፡


1

አንድ መስቀለኛ ክፍል ብቻ ስለሆነ ጥልቀት 1 ነው ፡፡

ቀረበ  

የዛፉን ከፍተኛ ጥልቀት ለማግኘት ቀለል ያለ የመልሶ ማልማት አካሄድ ማመልከት እንችላለን ፡፡ እያንዳንዱ የተግባር ጥሪ ‘ሥር’ ተብሎ የሚጠራ ሥር መስቀለኛ ሥፍራ ያለው ንዑስ ዛፍ ይወክላል። ዛፉን ከሥሩ መስቀለኛ ክፍል በመጀመር በድጋሜ ተግባር እናቋርጣለን።

ስለዚህ የመሠረቱ ጉዳይ ንዑሱ ዛፍ ባዶ ሲሆን ማለትም ሥሩ NULL ነው። ስለዚህ ጥልቀቱን እንደ 0 እንመለሳለን ፡፡

ሥሩ NULL ካልሆነ ለግራ ልጅ እና ለቀኝ ልጅ እንደገና ተመሳሳይ ተግባር ይደውሉ ፡፡

በስዕሉ ላይ እንደሚታየው የሁለቱ ልጆች ተግባር ጥልቀቱን ሲመልስ ከእነዚህ ሁለት ንዑስ ክፍሎች ውስጥ ከፍተኛውን እንመርጣለን እና 1 ን ከጨመርን በኋላ ይህንን እሴት እንመልሳለን (የሁለቱ ንዑስ ክፍል ወላጅ የሆነውን የአሁኑን መስቀለኛ መንገድ ማከል) ፡፡

ተመልከት
K ባዶ ቦታዎች LeetCode

የሁለትዮሽ ዛፍ ከፍተኛ ጥልቀትጭንቅላታም መያያዣ መርፌ

አፈጻጸም  

የ C ++ መርሃግብር ለ ‹ቢንሪ ዛፍ› Leetcode መፍትሔ ከፍተኛ ጥልቀት

#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

የጃቫ ፕሮግራም ለቢኒየር ዛፍ Leetcode መፍትሔ ከፍተኛ ጥልቀት

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 ጊዜዎች (የዛፉ ቁመት) ይከሰታል። ስለዚህ ከፍተኛው የጥሪ ቁልል መጠን O (N) ይሆናል።
በጥሩ ሁኔታ (ዛፉ ሙሉ በሙሉ ሚዛናዊ ነው) ፣ የዛፉ ቁመት ሎግ⁡ (N) ይሆናል። ስለዚህ ፣ በዚህ ጉዳይ ላይ ያለው የቦታ ውስብስብነት O (log⁡ (N)) ይሆናል።