Für jeden Knoten in einem ausgeglichenen Binärbaum beträgt der maximale Höhenunterschied zwischen dem linken untergeordneten Teilbaum und dem rechten untergeordneten Teilbaum höchstens 1.

Die Höhe eines Binärbaums ist der Abstand vom Wurzelknoten zum untergeordneten Knoten, der am weitesten von der Wurzel entfernt ist.

Unten ist ein Beispiel:

           2 <-- root: Height 1
          / \
         7   5 <-- Height 2
        / \   \
       2   6   9 <-- Height 3
          / \  /
         5  11 4 <-- Height 4 

Höhe des Binärbaums: 4

Die folgenden sind Binärbäume und ein Bericht darüber, ob sie ausgeglichen sind oder nicht:

Der Baum darüber ist unausgeglichen .

Der obige Baum ist ausgeglichen .

Schreiben Sie das kürzestmögliche Programm, das die Wurzel eines Binärbaums als Eingabe akzeptiert und einen falschen Wert zurückgibt, wenn der Baum unausgeglichen ist, und einen wahren Wert, wenn der Baum ausgeglichen ist.

Eingang

Die Wurzel eines binären Baumes. Dies kann in Form eines Verweises auf das Stammobjekt oder sogar einer Liste erfolgen, die eine gültige Darstellung eines Binärbaums darstellt.

Ausgabe

Gibt den Wahrheitswert zurück: Wenn der Baum ausgeglichen ist

Gibt einen falschen Wert zurück: Wenn der Baum nicht ausgeglichen ist.

Definition eines binären Baumes

Ein Baum ist ein Objekt, das einen Wert und entweder zwei andere Bäume oder Zeiger darauf enthält.

Die Struktur des Binärbaums sieht ungefähr so ​​aus:

typedef struct T
{
   struct T *l;
   struct T *r;
   int v;
}T;

Wenn Sie eine Listendarstellung für einen Binärbaum verwenden, sieht diese möglicherweise folgendermaßen aus:

[root_value, left_node, right_node]

Jelly , 11 Bytes

ḊµŒḊ€IỊ;߀Ạ

Probieren Sie es online!

Der leere Baum wird durch dargestellt [].

Prolog (SWI) , 49 Bytes

N+_/B/C:-X+B,Y+C,abs(X-Y)<2,N is max(X,Y)+1.
0+e.

Probieren Sie es online!

Stellt Bäume als dar Value/Left_Child/Right_Child, wobei der leere Baum das Atom ist e. Definiert +/2, welche Ergebnisse durch Erfolg oder Misserfolg ausgegeben werden , wobei sich links eine ungebundene Variable (oder eine Variable, die bereits der Höhe des Baums entspricht) und rechts der Baum befinden. Wenn das Argument height nicht akzeptabel ist, fügen Sie 9 Bytes zur Definition hinzu -T:-_+T..

N + _/B/C :-            % If the second argument is a tree of the form _Value/B/C,
    X+B,                % X is the height of its left child which is balanced,
    Y+C,                % Y is the height of its right child which is balanced,
    abs(X-Y) < 2,       % the absolute difference between X and Y is strictly less than 2,
    N is max(X,Y)+1.    % and N is the height of the full tree.
0 + e.                  % If, on the other hand, the second argument is e, the first is 0.

Wolfram Language (Mathematica) , 50 Byte

f@_[x_,y_]:=f@x&&f@y&&-2<Depth@x-Depth@y<2;f@_=1>0

Verwenden Sie Nullfür null value[left, right]für Knoten. Beispielsweise wird der folgende Baum als geschrieben 2[7[2[Null, Null], 6[5[Null, Null], 11[Null, Null]]], 5[Null, 9[4[Null, Null], Null]]].

    2
   / \
  7   5
 / \   \
2   6   9
   / \  /
  5  11 4

Probieren Sie es online!

Python 3.8 (Vorabversion) , 133 bis 125 Byte

b=lambda t:((max(l[0],r[0])+1,abs(l[0]-r[0])<2)if(l:=b(t[1]))[1]and(r:=b(t[2]))[1]else(0,0))if t else(0,1)
h=lambda t:b(t)[1]

Probieren Sie es online!

Nimmt einen Baum im "Listen" -Format: Ein Knoten ist [value, left, right]mit leftund rightals Knoten.

Rufen Sie die Funktion auf h.

Gibt 0oder Falsefür einen unausgeglichenen Baum zurück. Gibt 1oder Truefür einen ausgeglichenen Baum zurück.

Ungolfed:

# Returns tuple (current height, subtrees are balanced (or not))
def balanced(tree):
  if tree: # [] evaluates to False
    left = balanced(tree[1])
    right = balanced(tree[2])
    # If  the subtrees are not both balanced, nothing to do, just pass it up
    if left[1] and right[1]:
      height = max(left[0], right[0]) + 1
      subtrees_balanced = abs(left[0] - right[0]) < 2
    else:
      height = 0 # Value doesn't matter, will be ignored
      subtrees_balanced = False
  else:
    height = 0
    subtrees_balanced = True
  return (height, subtrees_balanced)

def h(tree):
  return balanced(tree)[1]

-10: Umgekehrte Logik, um nots loszuwerden

Wenn die Übernahme von Argumenten in der Mitte eines Aufrufs zulässig ist, kann dies auf (115 Byte) verkürzt werden.

(b:=lambda t:((max(l[0],r[0])+1,abs(l[0]-r[0])<2)if(l:=b(t[1]))[1]and(r:=b(t[2]))[1]else(0,0))if t else(0,1))(_)[1]

mit _ dem Baum zu überprüfen.

JavaScript (Node.js) , 49 Byte

h=([l,r])=>l?(d=h(l)-h(r))*d<2?1+h(d>0?l:r):NaN:1

Probieren Sie es online!

-9 Bytes von Arnauld.

JavaScript, 58 Byte

h=([l,r])=>l?(l=h(l),r=h(r),m=l>r?l:r,m+m-l-r<2?m+1:NaN):1

Probieren Sie es online!

Verwenden Sie []für Null und [left, right, value]für Knoten.

JavaScript, 162 Bytes

f=x=>{for(f=0,s=[[x,1]];s[0];){if(!((d=(t=s.pop())[0]).a&&d.b||f))f=t[1];if(f&&t[1]-f>1)return 0;if(d.a)s.push([d.a,t[1]+1]);if(d.b)s.push([d.b,t[1]+1])}return 1}

Probieren Sie es online!

Das Format der Eingabe ist ein Objekt

root={a:{node},b:{node},c:value}

Erläuterung

for(f=0,s=[[x,1]];s[0];){if(!((d=(t=s.pop())[0]).a&&d.b||f))f=t[1]

Wenn Sie eine Breitensuche durchführen, ermitteln Sie die Tiefe des ersten Knotens, dem ein oder mehrere Zweige fehlen.

if(f&&t[1]-f>1)return 0;if(d.a)s.push([d.a,t[1]+1]);if(d.b)s.push([d.b,t[1]+1])}

Setzen Sie die breiteste erste Suche fort und geben Sie Null zurück, wenn ein Element zwei tiefer ist als die Tiefe des ersten Knotens, in dem Verzweigungen fehlen.

return 1}

Wenn kein solcher Knoten gefunden wird, geben Sie 1 zurück

Julia, 56 Bytes

f(t)=t!=()&&(-(f.(t.c)...)^2<2 ? maximum(f,t.c)+1 : NaN)

Mit der folgenden Struktur, die den Binärbaum darstellt:

struct Tree
    c::NTuple{2,Union{Tree,Tuple{}}}
    v::Int
end

cist ein Tupel, das den linken und den rechten Knoten darstellt, und das leere Tupel ()wird verwendet, um die Abwesenheit eines Knotens anzuzeigen.

Falscher Wert ist NaN, jede ganze Zahl ist wahr.

Kotlin , 67 Bytes

fun N.c():Int=maxOf(l?.c()?:0,r?.c()?:0)+1
fun N.b()=l?.c()==r?.c()

Wo

data class N(val l: N? = null, val r: N? = null, val v: Int = 0)

Probieren Sie es online!

C 117 Bytes

h(T*r){r=r?1+h(h(r->l)>h(r->r)?r->l:r->r):0;}b(T*r){return r->l&&!b(r->l)||r->r&&!b(r->r)?0:abs(h(r->l)-h(r->r))<=1;}

Strukturelle Implementierung ist die folgende:

 typedef struct T
    {
        struct T * l;

        struct T * r;

        int v;

    } T;

Versuchen Sie dies auf JDoodle

Python 2 , 99 96 94 Bytes

lambda A:A==[]or(abs(D(A[1])-D(A[2]))<2)*f(A[1])*f(A[2])
D=lambda A:A>[]and-~max(map(D,A[1:]))

Probieren Sie es online!

3 Bytes von Jo King .

Nimmt die Eingabe als: leerer Knoten ist [], und andere Knoten sind [<value>, <leftNode>, <rightNode>]. Ausgänge 0/1für False / True.