இலக்கு கூட்டுத்தொகை தீர்வுகளுடன் இலை பாதைக்கு வேர்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் ஆப்பிள் பேஸ்புக் மைக்ரோசாப்ட்
ஆழம் முதல் தேடல் மரம்

ஒரு பைனரி மரம் மற்றும் ஒரு முழு எண் K வழங்கப்படுகிறது. மரத்தில் வேர்-க்கு-இலை பாதை இருக்கிறதா என்பதைத் திரும்பப் பெறுவதே எங்கள் குறிக்கோள், அதாவது தொகை இலக்கு-கேக்கு சமம். ஒரு பாதையின் கூட்டுத்தொகை அதில் உள்ள அனைத்து முனைகளின் கூட்டுத்தொகை ஆகும்.

இலக்கு கூட்டுத்தொகை தீர்வுகளுடன் இலை பாதைக்கு வேர்

    2
    
  /    \
  
1        4
 
       /     \

     1         4

K = 7
Path Present
     2
          
  /     \

1         4

       /     \

     1          3

K = 6
No such path

 

அணுகுமுறை

அணுகுமுறை மிகவும் எளிது. ஒரு குறிப்பிட்ட கட்டத்தில், ஒரு முனையின் மதிப்பு நமக்குத் தேவையானது, அது ஒரு இலை என்பதையும் நாம் சரிபார்க்கலாம். பின்னர், இலக்கு தொகையைக் கொண்ட ஒரு பாதை வேரிலிருந்து இந்த இடத்திற்கு உள்ளது என்று நாம் முடிவு செய்யலாம். எனவே, எந்தவொரு குழந்தைக்கும் நாம் மீண்டும் மீண்டும் செல்லும்போது, ​​இலக்கை முடிக்க மீதமுள்ள தொகையை நாம் அனுப்ப வேண்டும் என்பது உள்ளுணர்வு.

இந்த யோசனை ஒற்றை பாஸில் செயல்படுகிறது மரம்.

அல்காரிதம்

  1. ஒரு சுழல்நிலை உதவி செயல்பாட்டை உருவாக்கவும்
  2. உதவி செயல்பாட்டில் தற்போதைய முனை விவரங்கள் மற்றும் மீதமுள்ள தொகை உள்ளது
  3. தற்போதைய வேர் என்றால் ஏதுமில்லை,
    • திரும்ப தவறான, இந்த முனை எதையும் பங்களிக்க முடியாது என்பதால்.
  4. தற்போதைய வேர் என்றால் இல்லை
    • தேவையான தொகை முனை மதிப்புக்கு சமமாகவும், முனை ஒரு இலை என்றும் இருந்தால்
      • உண்மைக்குத் திரும்பு
    • வேறு
      • ஏதேனும் இடது அல்லது குழந்தை துணைத்தொகுப்பு தேவையான தொகையுடன் தேவையை பூர்த்திசெய்கிறதா என்று சரிபார்க்கவும்: current_sum - node_value
  5. வெளியீட்டை அச்சிடுக

நடைமுறைப்படுத்தல்

இலக்கு தொகையுடன் ரூட் டு இலை பாதையை கண்டுபிடிக்க சி ++ திட்டம்

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

bool pathSumEqualToTarget(treeNode* root , int target)
{
    if(!root)
        return false;
    if(target == root->value && !root->left && !root->right)
        return true;
    return pathSumEqualToTarget(root->left , target - root->value) || pathSumEqualToTarget(root->right , target - root->value);
}


int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right =  new treeNode(4);
    root->right->left = new treeNode(1);
    root->right->right = new treeNode(4);

    int K = 7;

    if(pathSumEqualToTarget(root , K))
        cout << "Path Present" << '\n';
    else
        cout << "No such path" << '\n';

}

 

இலக்கு தொகையுடன் ரூட் டு இலை பாதையை கண்டுபிடிக்க ஜாவா திட்டம்

class treeNode
{
    int value;
    treeNode left , right;

    public treeNode(int x)
    {
        value = x;
        left = right = null;
    }
}

class path_sum
{
    public static boolean pathSumEqualToTarget(treeNode root , int target)
    {
        if(root == null)
            return false;
        if(root.value == target && root.left == null && root.right == null)
            return true;
        return pathSumEqualToTarget(root.left , target - root.value) || pathSumEqualToTarget(root.right , target - root.value);
    }


    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(4);
        root.right.left = new treeNode(1);
        root.right.right = new treeNode(4);

        int K = 7;

        if(pathSumEqualToTarget(root , K))
            System.out.println("Path Present");
        else
            System.out.println("No such path");
    }
}

சிக்கலான பகுப்பாய்வு

இலக்கு தொகையுடன் ரூட் டு இலை பாதையை கண்டுபிடிப்பதற்கான நேரம் சிக்கலானது

ஓ (என்), பைனரி மரத்தின் ஒற்றை பாஸில் நிரல் மிக மோசமான நிலையில் செயல்படுவதால்.

இலக்கு தொகையுடன் ரூட் டு இலை பாதையை கண்டுபிடிக்க விண்வெளி சிக்கலானது

ஓ (ந). மறுநிகழ்வு துணை அடுக்கு இடத்தைப் பயன்படுத்துகிறது.