נתיב שורש לעלה עם סכום יעד פתרונות Leetcode  


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית תפוח עץ פייסבוק מיקרוסופט
אלגוריתמים קידוד עומק חיפוש ראשון ראיון אישי הוכחת ראיונות LeetCode LeetCodeSolutions עֵץ

בינארי עץ ומספר שלם K ניתן. המטרה שלנו היא להחזיר אם יש שביל שורש לעלה בעץ כך שסכומו שווה למטרה K. סכום הנתיב הוא סכום כל הצמתים המונחים עליו.

נתיב שורש לעלה עם סכום יעד פתרונות Leetcodeאורן

    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. הדפיסו את הפלט
ראה גם
עומק מקסימלי של פתרון Leetcode עץ N-ary

יישום  

תוכנית 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");
    }
}

ניתוח מורכבות  

מורכבות זמן למצוא נתיב שורש לעלה עם סכום יעד

עַל), שכן התוכנית עוברת במעבר יחיד של העץ הבינארי במקרה הגרוע ביותר.

מורכבות החלל למציאת נתיב שורש לעלה עם סכום יעד

עַל). רקורסיה משתמשת במרחב ערימה עזר.

1