ടാർ‌ഗെറ്റ് തുക ലീ‌കോഡ് സൊല്യൂഷനുകൾ‌ ഉപയോഗിച്ച് ലീഫ് പാതയിലേക്ക് റൂട്ട് ചെയ്യുക


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

ഒരു ബൈനറി വൃക്ഷം ഒരു പൂർണ്ണസംഖ്യ 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. The ട്ട്‌പുട്ട് പ്രിന്റുചെയ്യുക

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

ടാർഗെറ്റ് തുക ഉപയോഗിച്ച് റൂട്ട് ടു ലീഫ് പാത്ത് കണ്ടെത്തുന്നതിനുള്ള സി ++ പ്രോഗ്രാം

#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");
    }
}

സങ്കീർണ്ണത വിശകലനം

ടാർഗെറ്റ് തുക ഉപയോഗിച്ച് റൂട്ട് ടു ലീഫ് പാത്ത് കണ്ടെത്തുന്നതിനുള്ള സമയ സങ്കീർണ്ണത

O (N), ഏറ്റവും മോശം അവസ്ഥയിൽ ബൈനറി ട്രീയുടെ ഒരൊറ്റ പാസിൽ പ്രോഗ്രാം പ്രവർത്തിക്കുന്നതിനാൽ.

ടാർഗെറ്റ് തുക ഉപയോഗിച്ച് റൂട്ട് ടു ലീഫ് പാത്ത് കണ്ടെത്താനുള്ള സ്പേസ് കോംപ്ലക്സിറ്റി

O (N). ആവർത്തനം സഹായ സ്റ്റാക്ക് ഇടം ഉപയോഗിക്കുന്നു.