Root to Leaf path с целевата сума Leetcode Solutions


Ниво на трудност Лесно
Често задавани в Амазонка ябълка Facebook Microsoft
Дълбочина Първо търсене Дърво

Двоичен файл дърво и са дадени цяло число K. Нашата цел е да върнем дали в дървото има път от корен до лист, така че сумата му да е равна на целта-K. Сумата от пътя е сумата от всички възли, които лежат върху него.

Root to Leaf path с целевата сума 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. Ако текущият корен е НЕ Е НУЛНО
    • Ако необходимата сума е равна на стойността на възела и възелът е лист
      • return true
    • още
      • проверете дали някое ляво или дъщерно поддърво задоволява нуждата с необходимата сума: 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';

}

 

Програма Java за намиране на 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");
    }
}

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

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

НА), тъй като програмата работи в един проход на двоичното дърво в най-лошия случай.

Космическа сложност за намиране на корен до лист с целевата сума

НА). Рекурсията използва допълнително пространство на стека.