Патека од корен до лист со целна сума Leetcode Solutions


Ниво на тешкотија Лесно
Често прашувано во Амазон Јаболко Facebook Мајкрософт
Прво пребарување на длабочина Дрво

Бинарна дрво и даден е цел број К. Нашата цел е да вратиме дали има пат од корен до лист во дрвото, така што збирот е еднаков на целта-К. Збирот на патеката е збир на сите јазли што лежат на неа.

Патека од корен до лист со целна сума Leetcode Solutions

    2
    
  /    \
  
1        4
 
       /     \

     1         4

K = 7
Path Present
     2
          
  /     \

1         4

       /     \

     1          3

K = 6
No such path

 

Пристап

Пристапот е прилично едноставен. Можеме да провериме дека ако во одредена точка, вредноста на јазол е она што ни треба, а тоа е лист исто така. Потоа, можеме да заклучиме дека постои патека од коренот до оваа точка со целна сума. Значи, интуитивно е што додека рекурзивно скокаме кај кое било дете, мора да ја предадеме преостанатата сума за да ја завршиме целта.

Оваа идеја работи во едно поминување на дрво.

Алгоритам

  1. Создадете рекурзивна помошна функција
  2. Функцијата Помошник ги има деталите за тековниот јазол и преостанатата сума
  3. Ако тековниот корен е НУЛА,
    • се врати неточно бидејќи овој јазол не може да придонесе ништо.
  4. Ако тековниот корен е НЕМА НУТЕ
    • Ако потребната сума е еднаква на вредноста на јазолот, а јазолот е лист
      • вратете се вистинито
    • друго
      • проверете дали некое лево или дете под дрво ја задоволува потребата со потребната сума: current_sum - node_value
  5. Печатете го излезот

Имплементација

Програма C ++ за наоѓање на патека од корен до лист со целна сума

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

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

Временска комплексност да се најде патека од корен до лист со целна сума

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

Комплексност на вселената да се најде патека од корен до лист со целна сума

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