Бројање добрих чворова у решењу бинарног стабла са кодовима


Ниво тешкоће Средњи
Често питани у амазонка мицрософт
Бинарно дрво Дубина прва претрага

Изјава о проблему

У овом проблему а бинарно стабло даје се са својим кореном. Чвор Кс у стаблу назива се добрим ако у путањи од корена до Кс нема чворова чија је вредност већа од Кс.

Морамо вратити број добрих чворова у датом бинарном стаблу.

Пример

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

objašnjenje:

Бројање добрих чворова у решењу бинарног стабла са кодовима

Чворови у плавој боји су добри.
Роот Ноде (3) је увек добар чвор.
Чвор 4 -> (3,4) је максимална вредност на путањи која почиње од корена.
Чвор 5 -> (3,4,5) је максимална вредност у путањи
А Чвор 3 -> (3,1,3) је максимална вредност у путањи.

    3
   /
  3
 / \
4   2
3

objašnjenje:

Бројање добрих чворова у решењу бинарног стабла са кодовима

Чвор 2 -> (3, 3, 2) није добар, јер је „3“ већи од њега.

Приступ

Да бисмо утврдили да ли је чвор добар или не, морамо прећи путању од корена до тог чвора и проверити да ли његова вредност није мања од максималне на овој путањи.
Да бисмо пронашли број добрих чворова, морамо проверити овако за сваки чвор датог бинарног стабла. Али овде посматрајте једну ствар,

ако пронађемо одговор за одређени чвор прелазећи његову путању од корена, можемо отићи до његовог подређеног чвора такође одатле, јер смо већ прешли скоро путању до подређеног чвора, а такође имамо и максималну вредност до тада. Само морамо да ажурирамо максимум са тренутном вредношћу чвора да бисмо га пренели на оба подређена чвора.
Дакле, ово изгледа као ДФС или рекурзија где идемо до одређеног чвора прелазимо путању од корена до тог чвора. Стога ће у овом проблему рекурзија бити од велике помоћи. Кораци су:

  • Направите рекурзивну функцију са два аргумента као параметром. Једна је адреса чвора, а друга је максимална вредност коју смо овде пронашли.
  • Сад кад год будемо на одређеном чвору, проверићемо да ли је тренутна вредност чвора мања од тренутне макс. Ако није мањи, додаћемо овај чвор у свој анс и позвати исту функцију за његове подређене чворове након ажурирања максималне вредности.

Имплементација

Ц ++ програм за бројање добрих чворова у решењу бинарног стабла са кодовима

#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

Анализа сложености бројања добрих чворова у решењу бинарног стабла са кодовима

Сложеност времена

На) : где је н укупан број чворова у датом бинарном стаблу. Посећујемо сваки чвор једном.

Сложеност простора 

На) : Коришћени простор биће максимална величина стека рекурзије. У најгорем случају може доћи до величине О (н) у случају искривљеног бинарног стабла.