টার্গেটের যোগফল লেটকোড সমাধানগুলির সাথে রুট থেকে পাতার পথে


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক আপেল ফেসবুক মাইক্রোসফট
গভীরতা প্রথম অনুসন্ধান গাছ

একটি বাইনারি বৃক্ষ এবং একটি পূর্ণসংখ্যা কে দেওয়া হয়। আমাদের লক্ষ্যটি গাছটিতে শিকড় থেকে পাতাগুলির কোনও পথ রয়েছে কিনা তা ফেরত দেওয়া, এটির যোগফল লক্ষ্যমাত্রার কে সমান। কোনও পাথের যোগফল এটিতে থাকা সমস্ত নোডের যোগফল।

টার্গেটের যোগফল লেটকোড সমাধানগুলির সাথে রুট থেকে পাতার পথে

    2
    
  /    \
  
1        4
 
       /     \

     1         4

K = 7
Path Present
     2
          
  /     \

1         4

       /     \

     1          3

K = 6
No such path

 

অভিগমন

পদ্ধতিটি বেশ সহজ। আমরা এটি পরীক্ষা করতে পারি যে যদি একটি নির্দিষ্ট সময়ে, নোডের মান আমাদের যা প্রয়োজন তা হ'ল এবং এটি একটি পাতও। তারপরে, আমরা উপসংহারে পৌঁছে যেতে পারি যে লক্ষ্যটি যোগফলের মূল থেকে মূল পর্যন্ত এই বিন্দুতে একটি পথ বিদ্যমান। সুতরাং, এটি স্বজ্ঞাত যে আমরা যে কোনও শিশুকে পুনরাবৃত্তভাবে লাফিয়ে উঠতে পারি, লক্ষ্যটি শেষ করতে আমাদের অবশ্যই বাকি পরিমাণটি পাস করতে হবে।

এই ধারণাটি একক পাসে কাজ করে বৃক্ষ.

অ্যালগরিদম

  1. একটি পুনরাবৃত্ত সহায়ক সহায়ক ফাংশন তৈরি করুন
  2. সহায়ক ফাংশনটিতে বর্তমান নোডের বিশদ এবং বাকী যোগফল রয়েছে
  3. যদি বর্তমান মূল হয় খালি,
    • প্রত্যাবর্তন মিথ্যা, যেহেতু এই নোড কিছুই অবদান রাখতে পারে না।
  4. যদি বর্তমান মূল হয় নাল না
    • প্রয়োজনীয় যোগফল যদি নোডের সমান হয় এবং নোড একটি পাতা হয়
      • সত্য ফিরে
    • আর
      • কোনও বাম বা শিশু সাবট্রি প্রয়োজনীয় পরিমাণের সাথে প্রয়োজনীয়তা পূরণ করে কিনা তা পরীক্ষা করুন: কারেন্ট_সাম - নোড_ভ্যালু
  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");
    }
}

জটিলতা বিশ্লেষণ

টার্গেটের যোগফলের সাথে রুট থেকে পাতার পথে সন্ধানের জন্য জটিল জটিলতা

চালু), প্রোগ্রামটি সবচেয়ে খারাপ ক্ষেত্রে বাইনারি গাছের একক পাসে কাজ করে।

লক্ষ্য যোগফলের সাথে রুট থেকে লিফের পাথের সন্ধান করতে স্পেস জটিলতা

চালু). পুনরাবৃত্তি সহায়তার স্ট্যাক স্পেস ব্যবহার করে।