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


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

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

આ સમસ્યામાં એ દ્વિસંગી વૃક્ષ તેના મૂળ સાથે આપવામાં આવે છે. ઝાડમાં નોડ X ને સારું નામ આપવામાં આવ્યું છે જો મૂળથી X સુધીના પાથમાં X કરતા વધારે મૂલ્યવાળા કોઈ ગાંઠો નથી.

આપેલ દ્વિસંગી વૃક્ષમાં આપણે સારા ગાંઠોની સંખ્યા પરત કરવી પડશે.

ઉદાહરણ

    3
   / \
  1   4
 /   / \
3   1   5
4

સમજૂતી:

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

વાદળી રંગમાં ગાંઠો સારા છે.
રુટ નોડ (3) હંમેશાં સારો નોડ હોય છે.
નોડ 4 -> (3,4) એ મૂળથી શરૂ થતાં માર્ગમાં મહત્તમ મૂલ્ય છે.
નોડ 5 -> (3,4,5) એ પાથનું મહત્તમ મૂલ્ય છે
અને નોડ 3 -> (3,1,3) એ પાથનું મહત્તમ મૂલ્ય છે.

    3
   /
  3
 / \
4   2
3

સમજૂતી:

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

નોડ 2 -> (3, 3, 2) સારું નથી, કારણ કે "3" તેના કરતા વધારે છે.

અભિગમ

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

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

  • તેના પરિમાણ તરીકે બે દલીલો સાથે રિકર્સીવ ફંક્શન બનાવો. એક, નોડનું સરનામું અને બીજું અહીં સુધી આપણે મળેલ મહત્તમ મૂલ્ય છે.
  • હવે જ્યારે પણ આપણે કોઈ ચોક્કસ નોડ પર હોઈશું ત્યારે તપાસ કરીશું કે વર્તમાન નોડ મૂલ્ય વર્તમાન મેક્સમ કરતાં નાનું છે કે નહીં. જો તે નાનું ન હોય તો અમે આ ગાંઠોને અમારા જવાબોમાં ઉમેરીશું અને મહત્તમ મૂલ્યને અપડેટ કર્યા પછી તેના ચાઇલ્ડ નોડ્સ માટે સમાન ફંક્શનને ક callલ કરીશું.

અમલીકરણ

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

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left,*right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int rec(TreeNode* root, int mx)
{
   if(!root) return 0;

    int cur=0;
    if(mx <= root->val) cur++;

    mx=max(mx,root->val);
    return rec(root->left,mx) + rec(root->right,mx) + cur;
}

int goodNodes(TreeNode* root) {

    int mx= INT_MIN;
    return rec(root,mx);
}

int main() 
{
    TreeNode* root= new TreeNode(3);
    root->left=  new TreeNode(1);
    root->right=  new TreeNode(4);
    root->left->left=  new TreeNode(3);
    root->right->left=  new TreeNode(1);
    root->right->right=  new TreeNode(5);
    
    cout<< goodNodes(root) ;
    return 0; 
}
4

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

class Rextester{
    
static class TreeNode {
    int val;
    TreeNode left,right;
    TreeNode(int x)  {
        val=x;
        left=null;
        right=null;
    }
}
    
    static int rec(TreeNode root, int mx)
    {
        if(root==null) return 0;
        
        int cur=0;
        if(mx <= root.val) cur++;
        
        mx = Math.max(mx,root.val);
        return rec(root.left,mx) + rec(root.right,mx) + cur;
    }
    
    public static int goodNodes(TreeNode root) 
    {     
        int mx= Integer.MIN_VALUE;
        return rec(root,mx);       
    }
    
  public static void main(String args[])
    {
        TreeNode root= new TreeNode(3);
        root.left=  new TreeNode(1);
        root.right=  new TreeNode(4);
        root.left.left=  new TreeNode(3);
        root.right.left=  new TreeNode(1);
        root.right.right=  new TreeNode(5);
        
        System.out.println( goodNodes(root) );
    }
}
4

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

સમય જટિલતા

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

અવકાશ જટિલતા 

ઓ (એન): વપરાયેલી જગ્યા પુનરાવર્તન સ્ટેકનું મહત્તમ કદ હશે. ખરાબમાં, સ્ક્વિડ બાઈનરી ટ્રીના કિસ્સામાં તે ઓ (એન) કદમાં જઈ શકે છે.