Cerință
Decide dacă fiecare nod are numai valori strict mai mici în subarborele stâng și strict mai mari în subarborele drept. Condiția privește toți descendenții, nu doar copiii direcți.
Tip de problemă: Validate Binary Search Tree.
Date de intrare
n, apoi pentru nodurile 1..n câte o linie: valoare copil_stâng copil_drept. Rădăcina este 1; 0 înseamnă copil absent.
Date de ieșire
1 dacă arborele este BST strict, altfel 0.
Restricții
1 ≤ n ≤ 100. Legăturile descriu un arbore binar valid și conex, fără cicluri. |valoare| ≤ 1000000000; duplicatele fac ordinea strictă invalidă.
Observații
Selecție Algo25 pentru pregătirea interviurilor. Enunț, exemple și soluții originale.
Reper tematic pentru pregătire: https://www.hackerrank.com/interview/interview-preparation-kit
Exemple
2 EXEMPLEExemplul 1
Exemplul 1, reprezentat vizual. Toți descendenții din stânga lui 5 trebuie să fie mai mici decât 5; toți cei din dreapta, mai mari. Regula se aplică fiecărui nod.Mărește schema ↗Date de intrare
3
5 2 3
2 0 0
9 0 0
Date de ieșire
1
Exemplul 2
Date de intrare
4
5 2 3
1 0 0
7 4 0
4 0 0
Date de ieșire
0
Ai nevoie de un indiciu?
Descoperă doar cât îți trebuie. Indiciile nu scad punctajul.
Trimite o soluție
Se verifică autentificarea…
Deschide atelierul cu sugestii și teste locale în 4 limbaje →