Роот до Леаф патх са циљним збиром Леетцоде Солутионс  


Ниво тешкоће Лако
Често питани у амазонка јабука фацебоок мицрософт
алгоритми шифрирање Дубина прва претрага Интервју интервјупреп ЛеетЦоде ЛеетЦодеСолутионс Дрво

Бинарни дрво и дати су цео број К. Циљ нам је да вратимо да ли у стаблу постоји путања од корена до листа таква да је њен збир једнак циљу-К. Збир путање је збир свих чворова који леже на њој.

Роот до Леаф патх са циљним збиром Леетцоде СолутионсПин

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

Анализа сложености  

Сложеност времена за проналажење путање од корена до листа са циљаном сумом

НА), јер програм у најгорем случају ради у једном пролазу бинарног стабла.

Сложеност простора за проналажење путање од корена до листа са циљаном сумом

НА). Рекурзија користи помоћни простор стека.

1