រាប់ថ្នាំងល្អ ៗ ក្នុងសូលុយស្យុងមែកធាងឡេតូលេខកូដ


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

សេចក្តីថ្លែងការណ៍បញ្ហា។

ក្នុងបញ្ហានេះក មែកធាងគោលពីរ ត្រូវបានផ្តល់ឱ្យជាមួយឬសរបស់វា។ ថ្នាំង X នៅក្នុងមែកធាងត្រូវបានគេដាក់ឈ្មោះថាល្អប្រសិនបើនៅក្នុងផ្លូវពីឫសដល់ X គ្មានថ្នាំងណាដែលមានតម្លៃធំជាង X ។

យើងត្រូវប្រគល់ចំនួនថ្នាំងល្អ ៗ នៅក្នុងមែកធាងគោលពីរដែលបានផ្តល់ឱ្យ។

ឧទាហរណ៍

    3
   / \
  1   4
 /   / \
3   1   5
4

ការពន្យល់:

រាប់ថ្នាំងល្អ ៗ ក្នុងសូលុយស្យុងមែកធាងឡេតូលេខកូដ

ថ្នាំងដែលមានពណ៌ខៀវគឺល្អ។
ថ្នាំងឫស (៣) តែងតែជាថ្នាំងល្អ។
ថ្នាំង ៤ -> (៣,៤) គឺជាតម្លៃអតិបរមានៅក្នុងផ្លូវដែលចាប់ផ្តើមពីឫស។
ថ្នាំង 5 -> (3,4,5) គឺជាតម្លៃអតិបរមានៅក្នុងផ្លូវ
ហើយថ្នាំង ៣ -> (៣,១,៣) គឺជាតម្លៃអតិបរមានៅក្នុងផ្លូវ។

    3
   /
  3
 / \
4   2
3

ការពន្យល់:

រាប់ថ្នាំងល្អ ៗ ក្នុងសូលុយស្យុងមែកធាងឡេតូលេខកូដ

ថ្នាំង ២ -> (៣, ៣, ២) មិនល្អទេពីព្រោះ“ ៣” ខ្ពស់ជាងវា។

វិធីសាស្រ្ត

ដើម្បីដឹងថាតើថ្នាំងមួយល្អឬអត់យើងត្រូវត្រួសត្រាយផ្លូវពីឫសទៅថ្នាំងនោះហើយពិនិត្យមើលថាតើតម្លៃរបស់វាមិនតូចជាងអតិបរិមានៅក្នុងផ្លូវនេះទេ។
ដើម្បីរកចំនួនថ្នាំងល្អយើងត្រូវពិនិត្យមើលដូចនេះសម្រាប់ថ្នាំងនីមួយៗនៃមែកធាងគោលពីរដែលបានផ្តល់ឱ្យ។ ប៉ុន្តែនៅទីនេះសង្កេតរឿងមួយ

ប្រសិនបើយើងរកចម្លើយសម្រាប់ថ្នាំងជាក់លាក់មួយដោយឆ្លងកាត់ផ្លូវរបស់វាពីឫសយើងអាចទៅថ្នាំងកូនរបស់វាពីទីនោះដោយខ្លួនវាដែរពីព្រោះយើងបានឆ្លងកាត់ស្ទើរតែផ្លូវនៃថ្នាំងកុមារហើយយើងក៏មានតម្លៃអតិបរមារហូតដល់មិនទាន់។ យើងគ្រាន់តែត្រូវធ្វើបច្ចុប្បន្នភាពអតិបរមាជាមួយនឹងតម្លៃថ្នាំងបច្ចុប្បន្នដើម្បីផ្ទេរទៅថ្នាំងកូនទាំងពីរ។
ដូច្នេះនេះមើលទៅដូចជាឌីអេសអេសឬការហៅទៅកន្លែងណាដែលត្រូវទៅថ្នាំងជាក់លាក់មួយដែលយើងឆ្លងកាត់ផ្លូវពីឫសទៅថ្នាំងនោះ។ ដូច្នេះនៅក្នុងបញ្ហានេះការហៅឡើងវិញនឹងមានប្រយោជន៍ខ្លាំងណាស់។ ជំហានគឺ៖

  • បង្កើតមុខងារហៅខ្លួនឯងជាមួយអាគុយម៉ង់ពីរដែលជាប៉ារ៉ាម៉ែត្ររបស់វា។ មួយគឺជាអាសយដ្ឋានរបស់ថ្នាំងហើយទីពីរគឺជាតម្លៃអតិបរមាដែលយើងរកឃើញនៅទីនេះ។
  • ឥឡូវនេះនៅពេលណាដែលយើងស្ថិតនៅថ្នាំងជាក់លាក់មួយយើងនឹងពិនិត្យមើលថាតើតម្លៃថ្នាំងបច្ចុប្បន្នតូចជាងអតិបរិមាបច្ចុប្បន្នដែរឬទេ។ ប្រសិនបើវាមិនតូចជាងនេះយើងនឹងបន្ថែមថ្នាំងនេះទៅក្នុងចំលើយរបស់យើងហើយហៅមុខងារដដែលសម្រាប់ថ្នាំងកូនរបស់វាបន្ទាប់ពីធ្វើបច្ចុប្បន្នភាពតម្លៃអតិបរមា។

ការអនុវត្តន៍

កម្មវិធី C ++ សំរាប់រាប់ថ្នាំងល្អ ៗ ក្នុងសឺមីធូដិនធូរីសដំណោះស្រាយ

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left,*right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int rec(TreeNode* root, int mx)
{
   if(!root) return 0;

    int cur=0;
    if(mx <= root->val) cur++;

    mx=max(mx,root->val);
    return rec(root->left,mx) + rec(root->right,mx) + cur;
}

int goodNodes(TreeNode* root) {

    int mx= INT_MIN;
    return rec(root,mx);
}

int main() 
{
    TreeNode* root= new TreeNode(3);
    root->left=  new TreeNode(1);
    root->right=  new TreeNode(4);
    root->left->left=  new TreeNode(3);
    root->right->left=  new TreeNode(1);
    root->right->right=  new TreeNode(5);
    
    cout<< goodNodes(root) ;
    return 0; 
}
4

កម្មវិធីចាវ៉ាសំរាប់រាប់ថ្នាំងល្អ ៗ ក្នុងសូលុយស្យុងមែកធាងឡេតូឌុប

class Rextester{
    
static class TreeNode {
    int val;
    TreeNode left,right;
    TreeNode(int x)  {
        val=x;
        left=null;
        right=null;
    }
}
    
    static int rec(TreeNode root, int mx)
    {
        if(root==null) return 0;
        
        int cur=0;
        if(mx <= root.val) cur++;
        
        mx = Math.max(mx,root.val);
        return rec(root.left,mx) + rec(root.right,mx) + cur;
    }
    
    public static int goodNodes(TreeNode root) 
    {     
        int mx= Integer.MIN_VALUE;
        return rec(root,mx);       
    }
    
  public static void main(String args[])
    {
        TreeNode root= new TreeNode(3);
        root.left=  new TreeNode(1);
        root.right=  new TreeNode(4);
        root.left.left=  new TreeNode(3);
        root.right.left=  new TreeNode(1);
        root.right.right=  new TreeNode(5);
        
        System.out.println( goodNodes(root) );
    }
}
4

ការវិភាគស្មុគស្មាញសម្រាប់រាប់ថ្នាំងល្អ ៗ ក្នុងសូលុយស្យុងមែកធាងប្រព័ន្ធគោលពីរ

ស្មុគស្មាញពេលវេលា

O (n)៖ ដែល n ជាចំនួនសរុបនៃថ្នាំងនៅក្នុងមែកធាងគោលពីរដែលបានផ្តល់។ យើងកំពុងមើលថ្នាំងនីមួយៗម្តង។

ភាពស្មុគស្មាញនៃលំហ 

O (n)៖ ទំហំដែលបានប្រើនឹងមានទំហំអតិបរមានៃជង់នៃការហៅខ្លួនឯង។ អាក្រក់បំផុតវាអាចទៅទំហំ O (n) ក្នុងករណីមានមែកធាងគោលពីរ។