ബൈനറി ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിൽ നല്ല നോഡുകൾ എണ്ണുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ മൈക്രോസോഫ്റ്റ്
ബൈനറി ട്രീ ആഴത്തിലുള്ള ആദ്യ തിരയൽ

പ്രശ്നം പ്രസ്താവന

ഈ പ്രശ്‌നത്തിൽ a ബൈനറി ട്രീ അതിന്റെ റൂട്ട് ഉപയോഗിച്ച് നൽകിയിരിക്കുന്നു. റൂട്ട് മുതൽ എക്സ് വരെയുള്ള പാതയിൽ എക്സിനേക്കാൾ വലിയ മൂല്യമുള്ള നോഡുകളില്ലെങ്കിൽ ട്രീയിലെ ഒരു നോഡ് എക്സ് നല്ലതാണ്.

തന്നിരിക്കുന്ന ബൈനറി ട്രീയിലെ നല്ല നോഡുകളുടെ എണ്ണം ഞങ്ങൾ നൽകണം.

ഉദാഹരണം

    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” അതിനെക്കാൾ ഉയർന്നതാണ്.

സമീപനം

ഒരു നോഡ് നല്ലതാണോ അല്ലയോ എന്ന് കണ്ടെത്താൻ, റൂട്ട് മുതൽ ആ നോഡിലേക്കുള്ള പാതയിലൂടെ സഞ്ചരിച്ച് ഈ പാതയിൽ അതിന്റെ മൂല്യം പരമാവധി കുറവല്ലേ എന്ന് പരിശോധിക്കണം.
നല്ല നോഡുകളുടെ എണ്ണം കണ്ടെത്താൻ, നൽകിയിരിക്കുന്ന ബൈനറി ട്രീയുടെ ഓരോ നോഡിനും ഞങ്ങൾ ഇതുപോലെ പരിശോധിക്കേണ്ടതുണ്ട്. എന്നാൽ ഇവിടെ ഒരു കാര്യം നിരീക്ഷിക്കുക,

ഒരു പ്രത്യേക നോഡിന് അതിന്റെ റൂട്ട് റൂട്ട് വഴി സഞ്ചരിച്ച് ഉത്തരം കണ്ടെത്തുകയാണെങ്കിൽ, നമുക്ക് അവിടെ നിന്ന് തന്നെ ചൈൽഡ് നോഡിലേക്ക് പോകാം, കാരണം ഞങ്ങൾ ഇതിനകം തന്നെ ചൈൽഡ് നോഡിന്റെ പാതയിലൂടെ സഞ്ചരിച്ചിട്ടുണ്ട്, മാത്രമല്ല ഇതുവരെയും സഞ്ചരിച്ച പരമാവധി മൂല്യം നമുക്കുണ്ട്. നിലവിലെ നോഡ് മൂല്യമുള്ള അതിന്റെ രണ്ട് കുട്ടികളുടെ നോഡിലേക്ക് മാറ്റുന്നതിന് ഞങ്ങൾ പരമാവധി അപ്‌ഡേറ്റ് ചെയ്യണം.
അതിനാൽ ഇത് ഒരു ഡി‌എഫ്‌എസ് അല്ലെങ്കിൽ ഒരു പ്രത്യേക നോഡിലേക്ക് പോകേണ്ട ആവർത്തനമായി തോന്നുന്നു, റൂട്ട് മുതൽ ആ നോഡിലേക്കുള്ള പാത ഞങ്ങൾ സഞ്ചരിക്കുന്നു. അതിനാൽ ഈ പ്രശ്‌നത്തിൽ ആവർത്തനം വളരെ സഹായകരമാകും. ഘട്ടങ്ങൾ ഇവയാണ്:

  • അതിന്റെ പാരാമീറ്ററായി രണ്ട് ആർഗ്യുമെന്റുകൾ ഉപയോഗിച്ച് ഒരു ആവർത്തന പ്രവർത്തനം സൃഷ്ടിക്കുക. ഒന്ന് നോഡിന്റെ വിലാസവും രണ്ടാമത്തേത് ഞങ്ങൾ ഇവിടെ വരെ കണ്ടെത്തിയ പരമാവധി മൂല്യവുമാണ്.
  • ഇപ്പോൾ ഞങ്ങൾ ഒരു പ്രത്യേക നോഡിലായിരിക്കുമ്പോഴെല്ലാം നിലവിലെ നോഡ് മൂല്യം നിലവിലെ മാക്സിനേക്കാൾ ചെറുതാണോ എന്ന് പരിശോധിക്കും. ഇത് ചെറുതല്ലെങ്കിൽ‌, ഞങ്ങൾ‌ ഈ നോഡ് ഞങ്ങളുടെ ആൻ‌സിലേക്ക് ചേർ‌ക്കുകയും പരമാവധി മൂല്യം അപ്‌ഡേറ്റുചെയ്‌തതിന്‌ ശേഷം അതിന്റെ ചൈൽ‌ഡ് നോഡുകൾ‌ക്ക് സമാന പ്രവർ‌ത്തനത്തെ വിളിക്കുകയും ചെയ്യും.

നടപ്പിലാക്കൽ

ബൈനറി ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിലെ നല്ല നോഡുകൾ എണ്ണുന്നതിനുള്ള സി ++ പ്രോഗ്രാം

#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

ബൈനറി ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിലെ നല്ല നോഡുകളുടെ എണ്ണത്തിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n): ഇവിടെ n എന്നത് തന്നിരിക്കുന്ന ബൈനറി ട്രീയിലെ മൊത്തം നോഡുകളുടെ എണ്ണം. ഞങ്ങൾ ഓരോ നോഡും ഒരു തവണ സന്ദർശിക്കുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (n): ഉപയോഗിച്ച ഇടം ആവർത്തന സ്റ്റാക്കിന്റെ പരമാവധി വലുപ്പമായിരിക്കും. വളഞ്ഞ ബൈനറി ട്രീയുടെ കാര്യത്തിൽ ഏറ്റവും മോശമായത് O (n) വലുപ്പത്തിലേക്ക് പോകാം.