Root to Leaf ბილიკი სამიზნე თანხით Leetcode Solutions


Რთული ტური Easy
ხშირად ეკითხებიან Amazon Apple Facebook microsoft
სიღრმისეული პირველი ძებნა ხე

ორობითი ხე და მოცემულია მთელი რიცხვი K. ჩვენი მიზანია დავაბრუნოთ არის თუ არა ხეში ფესვიდან ფოთლის გზა ისეთი, რომ მისი ჯამი ტოლი იყოს K- მიზნისა. ბილიკის ჯამი არის ყველა კვანძი, რომელიც მასზე მდებარეობს.

Root to Leaf ბილიკი სამიზნე თანხით Leetcode Solutions

    2
    
  /    \
  
1        4
 
       /     \

     1         4

K = 7
Path Present
     2
          
  /     \

1         4

       /     \

     1          3

K = 6
No such path

 

მიდგომა

მიდგომა საკმაოდ მარტივია. ჩვენ შეგვიძლია შეამოწმოთ, რომ თუ გარკვეულ მომენტში, კვანძის მნიშვნელობა არის ის, რაც ჩვენ გვჭირდება, და ეს არის ფოთოლიც. ამის შემდეგ, შეგვიძლია დავასკვნათ, რომ გზა არსებობს ფესვიდან ამ წერტილამდე, რომელსაც აქვს სამიზნე თანხა. ასე რომ, ინტუიტიურია, რომ როდესაც რეკურსიულად გადავდივართ ნებისმიერ ბავშვზე, უნდა გადავიტანოთ დარჩენილი თანხა მიზნის მისაღწევად.

ეს იდეა მუშაობს ერთი გადასასვლელიდან ხე.

ალგორითმი

  1. შექმენით რეკურსიული დამხმარე ფუნქცია
  2. დამხმარე ფუნქციას აქვს მიმდინარე კვანძის დეტალები და დარჩენილი ჯამი
  3. თუ ამჟამინდელი ფესვია NULL,
    • დაბრუნების ყალბი, რადგან ამ კვანძს ვერაფერი შეუწყო ხელი.
  4. თუ ამჟამინდელი ფესვია NULL არ არის
    • თუ საჭირო თანხა უდრის კვანძის მნიშვნელობას და კვანძი არის ფოთოლი
      • ნამდვილი დაბრუნება
    • სხვა
      • შეამოწმეთ, ხომ არ აკმაყოფილებს მარცხენა ან ბავშვის ქვედა ხე საჭიროებას საჭირო თანხით: current_sum - node_value
  5. დაბეჭდე შედეგი

განხორციელება

C ++ პროგრამა Root to Leaf ბილიკის მოსაძებნად სამიზნე თანხით

#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';

}

 

ჯავა პროგრამა, Root to Leaf ბილიკის დასადგენად, სამიზნე თანხით

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

სირთულის ანალიზი

დროის სირთულე, რომ იპოვოთ Root to Leaf ბილიკი სამიზნე თანხით

O (N), როგორც პროგრამა მუშაობს უარეს შემთხვევაში ორობითი ხის ერთ გადასასვლელში.

სივრცის სირთულე, რომ იპოვოთ Root to Leaf ბილიკი სამიზნე თანხით

O (N) Recursion იყენებს დამხმარე დასტის ადგილს.