ပစ်မှတ်ပေါင်းလဒ် Leetcode Solutions နှင့်အတူ Leaf လမ်းကြောင်းကိုမှ Root


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ Apple Facebook က Microsoft က
အနက်ရောင်ပထမရှာဖွေမှု သစ်ပင်

တစ် ဦး က binary သစ်ပင် နှင့်တစ်ခုကိန်း K သည်ပေးထားသည်။ ကျွန်ုပ်တို့၏ရည်မှန်းချက်မှာသစ်ပင်တွင်အမြစ်မှသစ်ရွက်လမ်းကြောင်းရှိမရှိပြန်လာရန်ဖြစ်သည်။ ၎င်းသည် sum သည် target-K နှင့်ညီသည်။ လမ်းကြောင်း၏ပေါင်းလဒ်သည်၎င်းပေါ်တွင်တည်ရှိသော node အားလုံး၏ပေါင်းလဒ်ဖြစ်သည်။

ပစ်မှတ်ပေါင်းလဒ် Leetcode Solutions နှင့်အတူ Leaf လမ်းကြောင်းကိုမှ Root

    2
    
  /    \
  
1        4
 
       /     \

     1         4

K = 7
Path Present
     2
          
  /     \

1         4

       /     \

     1          3

K = 6
No such path

 

ချဉ်းကပ်နည်း

အဆိုပါချဉ်းကပ်မှုတော်တော်လေးရိုးရှင်းပါသည်။ ကျွန်ုပ်တို့သည်တစ်ချိန်ချိန်တွင် node တစ်ခု၏တန်ဖိုးသည်ကျွန်ုပ်တို့လိုအပ်သောအရာဖြစ်ပြီး၎င်းသည်အရွက်တစ်ခုလည်းဖြစ်ကြောင်းစစ်ဆေးနိုင်သည်။ ထို့နောက်လမ်းကြောင်းတစ်ခုမှပစ်မှတ်စုစုပေါင်းရှိသည့်ဤအချက်အထိလမ်းကြောင်းတည်ရှိကြောင်းကျွန်ုပ်တို့ကောက်ချက်ချနိုင်သည်။ ထို့ကြောင့်မည်သည့်ကလေးကိုမဆိုထပ်ခါထပ်ခါခုန်တက်သည်နှင့်အမျှကျန်ရှိသည့်ပမာဏကိုရည်မှန်းပြီးမြောက်ရန်လိုအပ်သည်။

ဒီအယူအဆဟာတစ်ခုတည်းသောဖြတ်သန်းမှုမှာအလုပ်လုပ်ပါတယ် သစ်ပင်.

algorithm

  1. Recursive အထောက်အကူ function ကိုဖန်တီးပါ
  2. helper function တွင်လက်ရှိ node အသေးစိတ်နှင့်ကျန်ငွေများကိုပါရှိသည်
  3. လက်ရှိအမြစ်သည်ဆိုပါက null
    • ပြန်လာ , အယူမှား ဒီ node ကိုဘာမှအထောက်အကူမပြုနိုင်အဖြစ်။
  4. လက်ရှိအမြစ်သည်ဆိုပါက NULL မဟုတ်ပါဘူး
    • လိုအပ်သောပေါင်းလဒ်သည် node တန်ဖိုးနှင့်တူညီသောအရွက်ဖြစ်လျှင်
      • ပြန်လာပါ
    • အခြားသူ
      • လက်ဝဲ (သို့) ကလေး subtree သည်လိုအပ်ချက်ကိုဖြည့်ဆည်းပေးနိုင်မလားစစ်ဆေးပါ: current_sum - node_value
  5. output ကိုပုံနှိပ်ပါ

အကောင်အထည်ဖော်ရေး

R ++ to Leaf လမ်းကြောင်းကို target sum နှင့်ရှာရန် C ++ Program

#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 လမ်းကြောင်းကို target sum နှင့်ရှာရန် Java Program

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

သတ်မှတ်ထားသောပေါင်းလဒ်နှင့်အတူ Root to Leaf လမ်းကြောင်းကိုရှာရန်အချိန်ရှုပ်ထွေးခြင်း

အို (N)ပရိုဂရမ်သည်အဆိုးဆုံးအခြေအနေတွင် binary tree တစ်ခု၏ pass တစ်ခုတည်းတွင်အလုပ်လုပ်သည်။

Rlex to Leaf လမ်းကြောင်းကို target sum နှင့်ရှာရန် Space Complexity

အို (N) ။ Recursion အရန် stack အာကာသကိုအသုံးပြုသည်။