Hədəf cəmi Leetcode Solutions ilə yarpaq yoluna kök

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon alma Facebook microsoft
alqoritmlər kodlaşdırma Dərinlik İlk Axtarış müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions AğacBaxılıb 19

İkili ağac və K tam ədədi verilir. Məqsədimiz, ağacda bir kökdən bir yarpağa bir yol olub olmadığı, cəminin hədəf K-ə bərabər olmasını qaytarmaqdır. Yolun cəmi onun üzərində yerləşən bütün qovşaqların cəmidir.

Hədəf cəmi Leetcode Solutions ilə yarpaq yoluna kökPin

    2
    
  /    \
  
1        4
 
       /     \

     1         4

K = 7
Path Present
     2
          
  /     \

1         4

       /     \

     1          3

K = 6
No such path

 

Yanaşma

Yanaşma olduqca sadədir. Müəyyən bir nöqtədə bir düyünün dəyərinin bizə lazım olan şey olduğunu və bunun da bir yarpaq olduğunu yoxlaya bilərik. Bundan sonra, kökdən bu nöqtəyə hədəf cəmi olan bir yolun olduğu qənaətinə gələ bilərik. Beləliklə, hər hansı bir uşağa rekursiv şəkildə sıçrayarkən hədəfi başa çatdırmaq üçün qalan cəmi ötürməliyik.

Bu fikir bir keçiddə işləyir ağac.

Alqoritm

  1. Rekursiv köməkçi funksiyası yaradın
  2. Köməkçi funksiyası cari düyün detallarına və qalan cəmə malikdir
  3. Mövcud kök SIFIR,
    • qayıtmaq yanlış, çünki bu düyün heç bir şey edə bilməz.
  4. Mövcud kök NULL DEYİL
    • Tələb olunan cəm düyün dəyərinə bərabərdirsə və düyün yarpaqdırsa
      • doğru qayıt
    • daha
      • sol və ya uşaq alt ağacının tələb olunan məbləğlə tələbatı ödədiyini yoxlayın: current_sum - node_value
  5. Çıxışı çap edin

Həyata keçirilməsi

Hədəf cəmi ilə Yaprakdan Kökə yol tapmaq üçün C ++ Proqramı

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

}

 

Hədəf cəmi ilə Kökdən Yarpağa yol tapmaq üçün Java Proqramı

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

Mürəkkəblik təhlili

Hədəf cəmi ilə Kökdən Yarpağa yol tapmaq üçün vaxt mürəkkəbliyi

O (N), proqram ən pis vəziyyətdə ikili ağacın tək bir keçidində işlədiyinə görə.

Hədəf cəmi ilə Kökdən Yarpağa yol tapmaq üçün Məkan Mürəkkəbliyi

O (N). Rekursiya köməkçi yığın boşluğundan istifadə edir.

Şərh yaz

Translate »
1