లక్ష్య మొత్తం లీట్‌కోడ్ సొల్యూషన్స్‌తో లీఫ్ పాత్‌కు రూట్ చేయండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ ఆపిల్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> మైక్రోసాఫ్ట్
లోతు మొదటి శోధన ట్రీ

ఒక బైనరీ చెట్టు మరియు పూర్ణాంక K ఇవ్వబడుతుంది. చెట్టులో రూట్-టు-లీఫ్ మార్గం ఉందో లేదో తిరిగి ఇవ్వడం మా లక్ష్యం, అది మొత్తం లక్ష్యం-కెకు సమానం. ఒక మార్గం యొక్క మొత్తం దానిపై ఉన్న అన్ని నోడ్‌ల మొత్తం.

లక్ష్య మొత్తం లీట్‌కోడ్ సొల్యూషన్స్‌తో లీఫ్ పాత్‌కు రూట్ చేయండి

    2
    
  /    \
  
1        4
 
       /     \

     1         4

K = 7
Path Present
     2
          
  /     \

1         4

       /     \

     1          3

K = 6
No such path

 

అప్రోచ్

విధానం చాలా సులభం. ఒక నిర్దిష్ట సమయంలో, నోడ్ యొక్క విలువ మనకు అవసరమైతే, అది కూడా ఒక ఆకు అని మనం తనిఖీ చేయవచ్చు. అప్పుడు, లక్ష్యం మొత్తాన్ని కలిగి ఉన్న రూట్ నుండి ఈ పాయింట్ వరకు ఒక మార్గం ఉందని మేము నిర్ధారించగలము. కాబట్టి, మనం ఏ బిడ్డకైనా పునరావృతంగా దూకుతున్నప్పుడు, లక్ష్యాన్ని పూర్తి చేయడానికి మిగిలిన మొత్తాన్ని దాటాలి.

ఈ ఆలోచన యొక్క ఒకే పాస్లో పనిచేస్తుంది చెట్టు.

అల్గారిథం

  1. పునరావృత సహాయక ఫంక్షన్‌ను సృష్టించండి
  2. సహాయక ఫంక్షన్ ప్రస్తుత నోడ్ వివరాలు మరియు మిగిలిన మొత్తాన్ని కలిగి ఉంది
  3. ప్రస్తుత రూట్ ఉంటే శూన్య
    • తిరిగి తప్పుడు, ఈ నోడ్ దేనికీ తోడ్పడదు.
  4. ప్రస్తుత రూట్ ఉంటే NULL కాదు
    • అవసరమైన మొత్తం నోడ్ విలువకు సమానం మరియు నోడ్ ఒక ఆకు అయితే
      • నిజం తిరిగి
    • వేరే
      • ఏదైనా ఎడమ లేదా పిల్లల సబ్‌ట్రీ అవసరమైన మొత్తంతో అవసరాన్ని సంతృప్తిపరుస్తుందో లేదో తనిఖీ చేయండి: 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");
    }
}

సంక్లిష్టత విశ్లేషణ

లక్ష్య మొత్తంతో రూట్ టు లీఫ్ మార్గాన్ని కనుగొనడానికి సమయం సంక్లిష్టత

పై), ప్రోగ్రామ్ బైనరీ చెట్టు యొక్క ఒకే పాస్లో చెత్త సందర్భంలో పనిచేస్తుంది.

లక్ష్య మొత్తంతో రూట్ టు లీఫ్ మార్గాన్ని కనుగొనడానికి స్పేస్ కాంప్లెక్సిటీ

పై). పునరావృతం సహాయక స్టాక్ స్థలాన్ని ఉపయోగిస్తుంది.