Пребройте добрите възли в решението с двоично дърво Leetcode


Ниво на трудност M
Често задавани в Амазонка Microsoft
Двоично дърво Дълбочина Първо търсене

Декларация за проблема

В този проблем a двоично дърво се дава с корена си. Възел X в дървото се нарича добър, ако в пътя от корен до X няма възли със стойност, по-голяма от X.

Трябва да върнем броя на добрите възли в даденото двоично дърво.

Пример

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

Обяснение:

Пребройте добрите възли в решението с двоично дърво Leetcode

Възлите в синьо са добри.
Root Node (3) винаги е добър възел.
Възел 4 -> (3,4) е максималната стойност в пътя, започващ от корена.
Възел 5 -> (3,4,5) е максималната стойност в пътя
И възел 3 -> (3,1,3) е максималната стойност в пътя.

    3
   /
  3
 / \
4   2
3

Обяснение:

Пребройте добрите възли в решението с двоично дърво Leetcode

Възел 2 -> (3, 3, 2) не е добър, тъй като „3“ е по-висок от него.

Подход

За да открием дали даден възел е добър или не, трябва да преминем пътя от корен до този възел и да проверим дали стойността му не е по-малка от максималната в този път.
За да намерим броя на добрите възли, трябва да проверим така за всеки възел от даденото двоично дърво. Но тук наблюдавайте едно нещо,

ако намерим отговора за конкретен възел, като прекосим пътя му от корен, можем да отидем до неговия дъщерен възел също от там, защото вече сме преминали почти пътя на дъщерния възел и имаме и максимална стойност, пресечена досега. Просто трябва да актуализираме максимума с текущата стойност на възела, за да го прехвърлим и в двата му дъщерни възела.
Така че това изглежда като DFS или рекурсия, където да отидем до определен възел, ние пресичаме пътя от корен до този възел. По този начин в този проблем рекурсията ще бъде много полезна. Стъпките са:

  • Създайте рекурсивна функция с два аргумента като параметър. Единият е адресът на възела, а вторият е максималната стойност, която намерихме до тук.
  • Сега, когато се намираме на определен възел, ще проверяваме дали текущата стойност на възела е по-малка от текущата макс. Ако не е по-малък, ще добавим този възел към нашите ans и ще извикаме същата функция за неговите дъщерни възли след актуализиране на максималната стойност.

изпълнение

Програма C ++ за преброяване на добри възли в решение с двоично дърво с Leetcode

#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

Програма Java за преброяване на добри възли в решение с двоично дърво Leetcode

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

Анализ на сложността за преброяване на добри възли в решение на двоично дърво с Leetcode

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

На) : където n е общият брой възли в даденото двоично дърво. Посещаваме всеки възел веднъж.

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

На) : Използваното пространство ще бъде максималният размер на стека на рекурсията. В най-лошия случай може да стигне до O (n) размер в случай на изкривено двоично дърво.