பைனரி மரம் லீட்கோட் தீர்வில் நல்ல முனைகளை எண்ணுங்கள்  


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

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

இந்த சிக்கலில் ஒரு பைனரி மரம் அதன் மூலத்துடன் கொடுக்கப்பட்டுள்ளது. ரூட் முதல் எக்ஸ் வரையிலான பாதையில் எக்ஸ் விட பெரிய மதிப்புள்ள முனைகள் எதுவும் இல்லை என்றால் மரத்தில் ஒரு முனை எக்ஸ் நல்லது என்று பெயரிடப்பட்டது.

கொடுக்கப்பட்ட பைனரி மரத்தில் உள்ள நல்ல முனைகளின் எண்ணிக்கையை நாம் திருப்பித் தர வேண்டும்.

உதாரணமாக

    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

பைனரி மரம் லீட்கோட் தீர்வில் நல்ல முனைகளை எண்ணுவதற்கான சிக்கலான பகுப்பாய்வு  

நேர சிக்கலானது

ஓ (ந): n என்பது கொடுக்கப்பட்ட பைனரி மரத்தில் உள்ள மொத்த முனைகளின் எண்ணிக்கை. ஒவ்வொரு முனையையும் ஒரு முறை பார்வையிடுகிறோம்.

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

ஓ (ந): பயன்படுத்தப்படும் இடம் மறுநிகழ்வு அடுக்கின் அதிகபட்ச அளவாக இருக்கும். மோசமான நேரத்தில் அது வளைந்த பைனரி மரத்தின் விஷயத்தில் O (n) அளவுக்கு செல்லலாம்.

1