مسیر ریشه به برگ با مقدار هدف Leetcode Solutions


سطح دشواری ساده
اغلب در آمازون سیب فیس بوک مایکروسافت
عمق جستجو اول درخت

یک باینری درخت و یک عدد صحیح K داده می شود. هدف ما این است که برگردیم آیا یک مسیر ریشه به برگ در درخت وجود دارد به طوری که مقدار آن برابر با K- هدف باشد. مجموع یک مسیر مجموع تمام گره هایی است که روی آن قرار دارند.

مسیر ریشه به برگ با مقدار هدف Leetcode Solutions

    2
    
  /    \
  
1        4
 
       /     \

     1         4

K = 7
Path Present
     2
          
  /     \

1         4

       /     \

     1          3

K = 6
No such path

 

روش

روش بسیار ساده است. می توانیم بررسی کنیم که اگر در یک نقطه خاص باشد ، ارزش یک گره همان چیزی است که ما به آن نیاز داریم و همچنین یک برگ است. سپس ، می توان نتیجه گرفت که مسیری از ریشه تا این نقطه با مجموع هدف وجود دارد. بنابراین ، این شهودی است که وقتی ما به طور بازگشتی به سراغ هر کودکی می رویم ، باید مبلغ باقیمانده را برای تکمیل هدف تحویل دهیم.

این ایده در یک عبور از درخت.

الگوریتم

  1. یک تابع کمکی بازگشتی ایجاد کنید
  2. تابع Helper دارای جزئیات گره فعلی و مبلغ باقیمانده است
  3. اگر ریشه فعلی باشد خالی،
    • برگشت نادرست از آنجا که این گره نمی تواند چیزی را کمک کند.
  4. اگر ریشه فعلی باشد تهی نیست
    • اگر جمع مورد نیاز برابر با مقدار گره باشد و گره یک برگ باشد
      • درست برگرد
    • دیگر
      • بررسی کنید که آیا هر زیر شاخه چپ یا فرزند نیاز را با مجموع مورد نیاز برآورده می کند:
  5. خروجی را چاپ کنید

پیاده سازی

برنامه C ++ برای یافتن مسیر Root to Leaf با مجموع هدف

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

}

 

برنامه جاوا برای یافتن مسیر 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");
    }
}

تحلیل پیچیدگی

پیچیدگی زمان برای یافتن مسیر ریشه به برگ با جمع هدف

بر)، همانطور که برنامه در بدترین حالت در یک عبور از درخت باینری کار می کند.

پیچیدگی فضا برای یافتن مسیر ریشه به برگ با جمع هدف

بر). بازگشت از فضای پشته کمکی استفاده می کند.