Escriba el programa más corto para calcular la altura de un árbol binario

18

La altura de un árbol binario es la distancia desde el nodo raíz al nodo hijo que está más alejado de la raíz.

A continuación se muestra un ejemplo:

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

Altura del árbol binario: 4

Definición de un árbol binario

Un árbol es un objeto que contiene un valor entero con signo y otros dos árboles o punteros a ellos.

La estructura de la estructura del árbol binario se parece a la siguiente:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;

El reto:

Entrada

La raíz de un árbol binario.

Salida

El número que representa la altura de un árbol binario.

Suponiendo que se le da la raíz de un árbol binario como entrada, escriba el programa más corto que calcule la altura de un árbol binario y devuelva la altura. El programa con la menor cantidad de bytes (espacios en blanco de contabilidad) gana.

T. Salim
fuente
44
¿Qué toman los idiomas sin punteros?
Jonathan Allan
44
... pero entonces mi objeto de árbol podría tener una propiedad, digamos h. Podría ser mejor definir una estructura específica hecha solo de listas para el propósito de este desafío.
Jonathan Allan
11
@ T.Salim En el futuro, considere publicar primero en el sandbox .
wizzwizz4
1
Entonces, ¿es una representación válida una lista de longitud 3 [root_value, left_node, right_node]donde cada uno de los árboles binarios left_nodey right_nodetambién son aceptables? Será trivial en muchos idiomas, pero puede ser divertido en otros.
Jonathan Allan
3
¿Puedes editar la pregunta para incluir lo que constituye una estructura binaria válida? Quizás una definición como a tree is an object that contains a value and either two other trees or pointers to them. Una definición que incluya lenguajes sin objetos también sería buena también.
Jo King

Respuestas:

11

Jalea , 3 bytes

ŒḊ’

A Enlace monádico aceptar una lista que representa el árbol: [root_value, left_tree, right_tree], donde cada uno de left_treey right_treeson estructuras similares (vacía si es necesario), que da la altura.

Pruébalo en línea!

¿Cómo?

Bastante trivial en gelatina:

ŒḊ’ - Link: list, as described above
ŒḊ  - depth
  ’ - decremented (since leaves are `[value, [], []]`)
Jonathan Allan
fuente
Jonathon Allen, ese es un lenguaje interesante que estás usando. Como recién llegado, ¿puede proporcionar un enlace o una referencia a un sitio web que enseñe a las personas cómo usar Jelly?
T. Salim
44
Haga clic en el enlace en el encabezado: es un lenguaje de golf desarrollado por Dennis , uno de los moderadores del sitio.
Jonathan Allan
2
Me pregunto cuán controvertido sería representar una hoja en xlugar de [x, [], []]...
Erik the Outgolfer
@EriktheOutgolfer Para mantener la naturaleza del "puntero" y la "estructura" de la pregunta, creo que cada nodo debe tener la misma forma.
Jonathan Allan
10

Python 2 ,  35  33 bytes

Gracias a Arnauld por notar un descuido y ahorrar 4.

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

Una función recursiva aceptar una lista que representa el árbol: [root_value, left_tree, right_tree], donde cada uno de left_treey right_treeson estructuras similares (vacío si es necesario), que devuelve la altura.

Pruébalo en línea!

Tenga en cuenta que []volverá False, pero en Python False==0.

Jonathan Allan
fuente
¿Se le permite a la misma persona dar dos respuestas diferentes a la misma pregunta?
T. Salim
66
Sí, por supuesto, el golf es una competencia a nivel de idioma. Incluso una segunda entrada en el mismo idioma es a veces aceptable, si el enfoque es muy diferente.
Jonathan Allan
@Arnauld Guess so (asumí que los no enteros podrían estar presentes por alguna razón)
Jonathan Allan
6

Haskell, 33 bytes

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

Usando el tipo de árbol personalizado data T = L | N T T Int, que es el equivalente de Haskell de la estructura C dada en el desafío.

Pruébalo en línea!

nimi
fuente
6

Perl 6 , 25 bytes

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

La entrada es una lista de 3 elementos (l, r, v). El árbol vacío es la lista vacía.

Pruébalo en línea!

Explicación

{                       }  # 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

Solución anterior, 30 bytes

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

Pruébalo en línea!

nwellnhof
fuente
El &?BLOCKtruco es interesante, ¡pero es un par de bytes más corto para asignar el bloque a $!
Jo King
@JoKing No lo sé. Almacenar la solución del desafío en un entorno global volátil $!o $/me da ganas de hacer trampa
nwellnhof
(Ab) usando variables como $! y $ / es una práctica bastante estándar para jugar al golf P6.
user0721090601
6

05AB1E , 11 7 5 bytes

Δ€`}N

-4 bytes gracias a @ExpiredData .
-2 bytes gracias a @Grimy .

El formato de entrada es similar a la respuesta jalea: una lista que representa el árbol: [root_value, left_tree, right_tree], donde cada uno de left_treey right_treeson estructuras similares (opcionalmente vacío). Es decir, [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]representa el árbol de la descripción del desafío.

Pruébelo en línea o verifique algunos casos de prueba más .

Explicación:

Δ     # 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)

Tenga en cuenta que aunque 05AB1E está basado en 0, el bucle de cambios Δhace que el índice de salida sea correcto, ya que necesita una iteración adicional para verificar que ya no cambie.

Kevin Cruijssen
fuente
1
7 bytes?
Datos
@ExpiredData Ah, por supuesto ... ¡Gracias! :)
Kevin Cruijssen
1
5 bytes
Grimmy
@ Grimy Pensé que usar el índice fuera de un bucle solo funcionaba en el código heredado ... S: ¡Gracias!
Kevin Cruijssen
5

JavaScript (ES6),  35  33 bytes

Estructura de entrada: [[left_node], [right_node], value]

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

Pruébalo en línea!

Comentado

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
Arnauld
fuente
Parece que puedes guardar un byte con a&&-~.
Shaggy
1
@Shaggy Eso llevaría a comparaciones con indefinido .
Arnauld
4

C, 43 bytes

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

La estructura del árbol binario es la siguiente:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;
T. Salim
fuente
2
55 bytes ¡ Pruébelo en línea! ¡Algunos trucos de golf específicos para C están aquí!
ErikF
1
@ErikF o 45 bytes
Arnauld
2
43 bytes
nwellnhof
3
Si su envío se basa en indicadores, ¿puede agregarlos al encabezado de su envío?
Jo King
1
Basándose en @nwellnhof 42 bytes
ceilingcat
4

JavaScript (Node.js) , 32 bytes

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

Pruébalo en línea!

Usar el nombre en flatlugar de flatteno smooshes una gran idea para el golf de código.

Utilizando []para nodo nulo en el árbol y [left, right, value]para nodos. valueAquí hay un número entero.

tsh
fuente
3

Haskell, 28 bytes

Usando la siguiente definición de datos:

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

La altura es:

h(_:&x)=foldr(max.succ.h)0 x
Michael Klein
fuente
2

Esquema, 72 bytes

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

Versión más legible:

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

Usar listas del formulario (datos, izquierda, derecha) para representar un árbol. P.ej

   1
  / \
  2  3
 /\
 4 5

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

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

Pruébalo en línea!

Algodón Zachary
fuente
2

R , 51 bytes

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

Pruébalo en línea!

  • Entrada: una lista anidada en el formato:list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

  • Algoritmo: aplana iterativamente el árbol en un nivel hasta que se convierte en un vector plano: el recuento de iteraciones corresponde a la profundidad máxima.

Inspirado por solución @KevinCruijssen


Alternativa recursiva:

R , 64 bytes

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

Pruébalo en línea!

Redefine la función / operador '~' para que pueda calcular la profundidad máxima de un árbol almacenado en una estructura de lista.

La estructura de la lista de un árbol está en el formato: list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

  • -2 gracias a @Giuseppe
digEmAll
fuente
¿Por qué lo usas d=1y luego d-1al final? ¿No podrías empezar 0?
Giuseppe
También cambié >de ~ aquí por lo que los casos de prueba son más fáciles de entrada
Giuseppe
@Giuseppe: por supuesto ... me faltaba lo obvio 🤦‍♂️
digEmAll
1

K (ngn / k) , 4 bytes

Solución:

#,/\

Pruébalo en línea!

Explicación:

Creo que puedo haber perdido el punto.

Representando un árbol como la lista de 3 elementos (nodo principal; hijo izquierdo; hijo derecho), el ejemplo se puede representar como

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

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

Entonces, la solución es aplanar iterativamente y contar las iteraciones:

#,/\ / the solution
   \ / iterate
 ,/  / flatten
#    / count
callejero
fuente
0

Carbón , 29 bytes

⊞θ⁰⊞υθFυ«≔⊕⊟ιθFΦι∧κλ⊞υ⊞Oκθ»Iθ

Pruébalo en línea! El enlace es a la versión detallada del código. Modifica temporalmente el árbol durante el procesamiento. Explicación:

⊞θ⁰

Empuje cero al nodo raíz.

⊞υθ

Empuje el nodo raíz a la lista de todos los nodos.

Fυ«

Realice una búsqueda amplia del árbol.

≔⊕⊟ιθ

Obtenga la profundidad de este nodo.

FΦι∧κλ

Recorra cualquier nodo secundario.

⊞υ⊞Oκθ

Indique al nodo secundario la profundidad de su elemento primario y empújelo a la lista de todos los nodos.

»Iθ

Una vez que se hayan atravesado todos los nodos, imprima la profundidad del último nodo. Como el recorrido fue primero en anchura, esta será la altura del árbol.

Neil
fuente
0

Stax , 5 bytes

▐▌µ╡⌂

Ejecutar y depurarlo

Stax no tiene punteros ni valores nulos, por lo que represento la entrada como [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]. Tal vez sea una ventaja injusta, pero fue lo más cerca que pude llegar.

Desempaquetado, sin golf y comentado, el código se ve así.

        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

Ejecute este

recursivo
fuente
0

Kotlin, 45 bytes

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

Asumiendo que la siguiente clase está definida

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

Pruébalo en línea

Aso Leo
fuente
0

Julia, 27 bytes

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

Con la siguiente estructura que representa el árbol binario:

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

ces una tupla que representa los nodos izquierdo y derecho y la tupla vacía ()se usa para indicar la ausencia de un nodo.

usuario3263164
fuente
0

Kotlin , 42 bytes

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

Pruébalo en línea!

Dónde

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