Wysokość drzewa binarnego to odległość od węzła głównego do potomka węzła, który jest najdalej od korzenia.

Poniżej znajduje się przykład:

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

Wysokość drzewa binarnego: 4

Definicja drzewa binarnego

Drzewo to obiekt zawierający podpisaną wartość całkowitą i albo dwa inne drzewa, albo wskaźniki do nich.

Struktura binarnego drzewa struktury wygląda mniej więcej tak:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;

Wyzwanie:

Wejście

Korzeń drzewa binarnego

Wynik

Liczba reprezentująca wysokość drzewa binarnego

Zakładając, że jako dane wejściowe podano katalog główny drzewa binarnego, napisz najkrótszy program, który oblicza wysokość drzewa binarnego i zwraca wysokość. Wygrywa program z najmniejszą liczbą bajtów (białe znaki rozliczeniowe).

Galaretka , 3 bajty

ŒḊ’

Monadycznego link przyjmując listę reprezentujący drzewa: [root_value, left_tree, right_tree], gdzie każdy left_treei right_treesą podobne struktury (pusty w razie potrzeby), co daje wzrost.

Wypróbuj online!

W jaki sposób?

Całkiem trywialne w Galaretce:

ŒḊ’ - Link: list, as described above
ŒḊ  - depth
  ’ - decremented (since leaves are `[value, [], []]`)

Python 2 ,  35  33 bajtów

Dziękujemy Arnauldowi za zauważenie niedopatrzenia i oszczędność 4.

f=lambda a:a>[]and-~max(map(f,a))

Funkcji rekurencyjnej przyjmując listę reprezentujący drzewa: [root_value, left_tree, right_tree], gdzie każdy left_treei right_treesą podobne struktury (pusty w razie potrzeby), która zwraca wysokość.

Wypróbuj online!

^{Zauważ, że [] powróci False, ale w Pythonie False==0.}

Haskell, 33 bajty

h L=0 
h(N l r _)=1+max(h l)(h r)

Używanie niestandardowego typu drzewa data T = L | N T T Int, który jest odpowiednikiem struktury C Haskell podanej w wyzwaniu.

Wypróbuj online!

Perl 6 , 25 bajtów

{($_,{.[*;*]}...*eqv*)-2}

Dane wejściowe to lista 3-elementowa (l, r, v). Puste drzewo to pusta lista.

Wypróbuj online!

Wyjaśnienie

{                       }  # Anonymous block
    ,        ...  # Sequence constructor
  $_  # Start with input
     {.[*;*]}  # Compute next element by flattening one level
               # Sadly *[*;*] doesn't work for some reason
                *eqv*  # Until elements doesn't change
 (                   )-2  # Size of sequence minus 2

Stare rozwiązanie, 30 bajtów

{+$_&&1+max map &?BLOCK,.[^2]}

Wypróbuj online!

05AB1E , 11 7 5 bajtów

Δ€`}N

-4 bajty dzięki @ExpiredData .
-2 bajty dzięki @Grimy .

Format wejściowy jest podobny jako odpowiedź Jelly: wykaz reprezentujący drzewa: [root_value, left_tree, right_tree], gdzie każdy left_treei right_treesą podobne struktury (opcjonalnie pusty). To znaczy[2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]] Reprezentuje drzewo z opisu wyzwania.

Wypróbuj online lub sprawdź kilka innych przypadków testowych .

Wyjaśnienie:

Δ     # Loop until the (implicit) input-list no longer changes:
  €`  #  Flatten the list one level
}N    # After the loop: push the 0-based index of the loop we just finished
      # (which is output implicitly as result)

Zauważ, że chociaż 05AB1E jest oparty na 0, pętla zmian Δpowoduje, że indeks wyjściowy jest poprawny, ponieważ wymaga dodatkowej iteracji, aby sprawdzić, czy już się nie zmienia.

JavaScript (ES6),  35  33 bajtów

Struktura wejściowa: [[left_node], [right_node], value]

f=([a,b])=>a?1+f(f(a)>f(b)?a:b):0

Wypróbuj online!

Skomentował

f =                       // f is a recursive function taking
([a, b]) =>               // a node of the tree split into
                          // a[] = left child, b[] = right child (the value is ignored)
  a ?                     // if a[] is defined:
    1 +                   //   increment the final result for this branch
    f(                    //   and add:
      f(a) > f(b) ? a : b //     f(a) if f(a) > f(b) or f(b) otherwise
    )                     //
  :                       // else:
    0                     //   stop recursion and return 0

C, 43 bajty

h(T*r){r=r?1+(int)fmax(h(r->l),h(r->r)):0;}

Struktura drzewa binarnego jest następująca:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;

JavaScript (Node.js) , 32 bajty

f=a=>/,,/.test(a)&&f(a.flat())+1

Wypróbuj online!

Używanie nazwy flatzamiast flattenlub smooshto świetny pomysł na golfa kodowego.

Używanie []węzła zerowego w drzewie i [left, right, value]węzłów. valuetutaj jest liczba całkowita.

Wolfram Language (Mathematica) , 10 bajtów

Depth@#-2&

Wypróbuj online! Pobiera dane wejściowe jako zagnieżdżoną listę {v, l, r}.

Haskell, 28 bajtów

Korzystanie z następującej definicji danych:

data T a = (:&) a [T a]

Wysokość wynosi:

h(_:&x)=foldr(max.succ.h)0 x

Schemat, 72 bajty

(define(f h)(if(null? h)0(+ 1(max(f(car(cdr h)))(f(car(cdr(cdr h))))))))

Bardziej czytelna wersja:

(define (f h)
   (if (null? h)
      0
      (+ 1 
         (max
             (f (car (cdr h)))
             (f (car (cdr (cdr h))))
         )
      )
   )
)

Korzystanie z list formularza (dane, lewy, prawy) do reprezentowania drzewa. Na przykład

   1
  / \
  2  3
 /\
 4 5

is represented as: (1 (2 (4 () ()) (5 () ())) (3 () ())

(1
   (2
      (4 () ())
```   (5 () ())
   (3 () ())
)

Wypróbuj online!

R , 51 bajtów

function(L){while(is.list(L<-unlist(L,F)))T=T+1;+T}

Wypróbuj online!

• Dane wejściowe: lista zagnieżdżona w formacie:list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

• Algorytm: Iteracyjnie spłaszcza drzewo o jeden poziom, aż stanie się płaskim wektorem: liczba iteracji odpowiada maksymalnej głębokości.

Zainspirowany rozwiązaniem @KevinCruijssen

Rekurencyjna alternatywa:

R , 64 bajty

`~`=function(L,d=0)'if'(is.list(L),max(L[[2]]~d+1,L[[3]]~d+1),d)

Wypróbuj online!

Przedefiniowuje funkcję / operatora, '~'dzięki czemu jest w stanie obliczyć maksymalną głębokość drzewa przechowywanego w strukturze listy.

Struktura listy drzewa ma format: list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

• -2 dzięki @Giuseppe

Japt , 8 bajtów

@eU=c1}a

Spróbuj

Oryginał, 9 bajtów

Ω¡ÒßXÃrw

Spróbuj

K (ngn / k) , 4 bajty

Rozwiązanie:

#,/\

Wypróbuj online!

Wyjaśnienie:

Myślę, że mogłem nie zauważyć sedna.

Przykład reprezentujący drzewo jako listę 3-elementową (węzeł nadrzędny; lewy podrzędny; prawy podrzędny), przykład można przedstawić jako

(2;
  (7;
    (,2);
    (6;
      (,5);
      (,11)
    )
  );
  (5;
    ();
    (9;
      (,4);
      ()
    )
  )
)

lub: (2;(7;(,2);(6;(,5);(,11)));(5;();(9;(,4);()))) .

Rozwiązaniem jest iteracyjne spłaszczenie i policzenie iteracji:

#,/\ / the solution
   \ / iterate
 ,/  / flatten
#    / count

Węgiel drzewny , 29 bajtów

⊞θ⁰⊞υθＦυ«≔⊕⊟ιθＦΦι∧κλ⊞υ⊞Ｏκθ»Ｉθ

Wypróbuj online! Link jest do pełnej wersji kodu. Tymczasowo modyfikuje drzewo podczas przetwarzania. Wyjaśnienie:

⊞θ⁰

Wciśnij zero do węzła głównego.

⊞υθ

Wciśnij węzeł główny na listę wszystkich węzłów.

Ｆυ«

Wykonaj pierwsze wyszukiwanie drzewa.

≔⊕⊟ιθ

Uzyskaj głębokość tego węzła.

ＦΦι∧κλ

Pętla nad dowolnymi węzłami potomnymi.

⊞υ⊞Ｏκθ

Poinformuj węzeł potomny o jego głębokości nadrzędnej i pchnij go na listę wszystkich węzłów.

»Ｉθ

Po przejściu wszystkich węzłów wydrukuj głębokość ostatniego węzła. Ponieważ przejście było pierwsze, będzie to wysokość drzewa.

Stax , 5 bajtów

▐▌µ╡⌂

Uruchom i debuguj

Stax nie ma wskaźników ani wartości zerowych, więc reprezentuję dane wejściowe jak [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]] . Może to niesprawiedliwa przewaga, ale to było najbliższe, jakie mogłem uzyskać.

Kod po rozpakowaniu, niepolowaniu i komentowaniu wygląda tak.

        The input starts on top of the input stack
Z       Tuck a zero underneath the top value in the stack.  Both values end up on the main stack.
D       Drop the first element from array
F       For each remaining element (the leaves) run the rest of the program
  G^    Recursively call the entire program, then increment
  T     Get maximum of the two numbers now ow the stack

Uruchom ten

Kotlin, 45 bajtów

val Tree.h:Int get()=1+maxOf(l?.h?:0,r?.h?:0)

Zakładając, że zdefiniowano następującą klasę

class Tree(var v: Int, var l: Tree? = null, var r: Tree? = null)

Wypróbuj online

Julia, 27 bajtów

f(t)=t≢()&&maximum(f,t.c)+1

Z następującą strukturą reprezentującą drzewo binarne:

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

cto krotka reprezentująca lewy i prawy węzeł, a pusta krotka ()służy do sygnalizowania braku węzła.

Kotlin , 42 bajty

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

Wypróbuj online!

Gdzie

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