ចាក់ឬសដល់ផ្លូវស្លឹកជាមួយនឹងផលបូកគោលដៅ Leetcode ដំណោះស្រាយ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ផ្លែប៉ោម Facebook ក្រុមហ៊ុន Microsoft
ជម្រៅស្វែងរកដំបូង មែកធាង

គោលពីរ ដើមឈើ និងលេខគត់ 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. ប្រសិនបើឫសបច្ចុប្បន្នគឺ មិនមែនទេ
    • ប្រសិនបើផលបូកដែលត្រូវការគឺស្មើនឹងតម្លៃថ្នាំងហើយថ្នាំងគឺជាស្លឹក
      • ត្រឡប់ពិត។
    • ផ្សេងទៀត
      • ពិនិត្យមើលថាតើអនុក្រឹត្យខាងឆ្វេងឬកុមារពេញចិត្តនឹងតំរូវការដែលមានៈផលបូក - ចរន្ត - 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';

}

 

ចាវ៉ាកម្មវិធីដើម្បីរកផ្លូវទៅរកស្លឹកជាមួយផលបូកគោលដៅ

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

ការវិភាគស្មុគស្មាញ

ភាពស្មុគស្មាញនៃពេលវេលាដើម្បីរកផ្លូវទៅរកស្លឹកជាមួយផលបូកគោលដៅ

O (N)ដូចជាកម្មវិធីដំណើរការនៅក្នុងការឆ្លងកាត់តែមួយនៃមែកធាងគោលពីរក្នុងករណីដ៏អាក្រក់បំផុត។

ភាពស្មុគស្មាញក្នុងលំហដើម្បីរកផ្លូវទៅរកស្លឹកជាមួយនឹងផលបូកគោលដៅ

អូ (ន) ។ ការហៅឡើងវិញប្រើចន្លោះជង់ជំនួយ។