مسار الجذر إلى الورقة مع حلول Leetcode للمبلغ المستهدف  


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون أجهزة آبل Facebook Microsoft
خوارزميات الترميز عمق البحث الأول المقابلة الشخصية مقابلة LeetCode LeetCodeSolutions شجرة

ثنائي شجرة ويرد عدد صحيح ك. هدفنا هو إعادة ما إذا كان هناك مسار من الجذر إلى الورقة في الشجرة بحيث يكون المجموع مساويًا للهدف- K. مجموع المسار هو مجموع كل العقد التي تقع عليه.

مسار الجذر إلى الورقة مع حلول Leetcode للمبلغ المستهدف

    2
    
  /    \
  
1        4
 
       /     \

     1         4

K = 7
Path Present
     2
          
  /     \

1         4

       /     \

     1          3

K = 6
No such path

 

الرسالة  

النهج بسيط جدا. يمكننا التحقق مما إذا كانت قيمة العقدة في نقطة معينة هي ما نحتاجه ، وهي ورقة أيضًا. بعد ذلك ، يمكننا أن نستنتج أن المسار موجود من الجذر إلى هذه النقطة له المجموع المستهدف. لذلك ، من البديهي أننا عندما نقفز بشكل متكرر إلى أي طفل ، يجب علينا تمرير المبلغ المتبقي لإكمال الهدف.

تعمل هذه الفكرة في مسار واحد من شجرة.

خوارزمية  

  1. قم بإنشاء دالة مساعدة عودية
  2. تحتوي وظيفة المساعد على تفاصيل العقدة الحالية والمبلغ المتبقي
  3. إذا كان الجذر الحالي هو NULL،
    • عائد أعلى خاطئة، لأن هذه العقدة لا يمكنها المساهمة بأي شيء.
  4. إذا كان الجذر الحالي هو ليس فارغ
    • إذا كان المجموع المطلوب يساوي قيمة العقدة وكانت العقدة ورقة
      • عودة صحيح
    • آخر
      • تحقق مما إذا كانت أي شجرة فرعية يسارية أو فرعية تلبي الحاجة بالمبلغ المطلوب: current_sum - node_value
  5. اطبع الإخراج
انظر أيضا
أقصى عمق لمحلول N-ary Tree Leetcode

تطبيق  

برنامج 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 للعثور على مسار الجذر إلى الورقة بالمبلغ المستهدف

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

تحليل التعقيد  

تعقيد الوقت للعثور على مسار الجذر إلى الورقة بالمجموع المستهدف

على)حيث أن البرنامج يعمل في ممر واحد للشجرة الثنائية في أسوأ الحالات.

تعقيد الفضاء للعثور على مسار الجذر إلى الورقة بالمجموع المستهدف

على). يستخدم العودية مساحة مكدس إضافية.