Зорилтот нийлбэр Leetcode Solutions ашиглан навч руу чиглүүлнэ


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Apple-ийн Facebook-ийн Microsoft-
Гүнзгий анхны хайлт Мод

Хоёртын хувилбар мод ба 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. Туслах функц нь одоогийн зангилааны дэлгэрэнгүй мэдээлэл болон үлдсэн нийлбэртэй байна
  3. Хэрэв одоогийн үндэс бол NULL,
    • буцах хуурамч, Энэ зангилаа юу ч оруулж чадахгүй тул.
  4. Хэрэв одоогийн үндэс бол ҮГҮЙ
    • Шаардлагатай нийлбэр нь зангилааны утгатай тэнцүү бөгөөд зангилаа нь навч юм
      • үнэнийг буцаана
    • бас
      • Зүүн эсвэл хүүхдийн аль ч мод шаардлагатай нийлбэрээр хэрэгцээг хангаж байгаа эсэхийг шалгана уу: current_sum - node_value
  5. Гаралтыг хэвлэх

Хэрэгжүүлэх

Зорилтот нийлбэрээр Root to Leaf замыг олох програмыг 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';

}

 

Зорилтот нийлбэрээр Root to Leaf замыг олох 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");
    }
}

Нарийн төвөгтэй байдлын шинжилгээ

Зорилтот нийлбэрээр Навчис хүртэлх замыг олох цаг хугацааны нарийн төвөгтэй байдал

O (N), програм нь хамгийн муу тохиолдолд хоёртын модны нэг дамжуулалтанд ажилладаг тул.

Зорилтот нийлбэрээр үндэснээс навч хүртэлх замыг олох зайны нарийн төвөгтэй байдал

O (N). Рекурс нь туслах стекийн зайг ашигладаг.