Escreva o programa mais curto para calcular a altura de uma árvore binária

18

A altura de uma árvore binária é a distância do nó raiz ao filho do nó que está mais distante da raiz.

Abaixo está um exemplo:

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

Altura da árvore binária: 4

Definição de uma árvore binária

Uma árvore é um objeto que contém um valor inteiro assinado e duas outras árvores ou ponteiros para eles.

A estrutura da estrutura da árvore binária é semelhante à seguinte:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;

O desafio:

Entrada

A raiz de uma árvore binária

Resultado

O número que representa a altura de uma árvore binária

Supondo que você receba a raiz de uma árvore binária como entrada, escreva o programa mais curto que calcula a altura de uma árvore binária e retorna a altura. O programa com menos quantidade de bytes (espaços em branco de contabilidade) vence.

T. Salim
fonte
4
O que os idiomas sem ponteiros levam?
Jonathan Allan
4
... mas meu objeto de árvore poderia ter apenas uma propriedade, digamos h. Talvez seja melhor definir uma estrutura específica feita apenas de listas para o objetivo deste desafio.
Jonathan Allan
11
@ T.Salim No futuro, considere postar primeiro na sandbox .
wizzwizz4
1
Então, uma representação válida é uma lista de comprimento 3 em [root_value, left_node, right_node]que cada uma left_nodee right_nodetambém são árvores binárias aceitáveis? Será trivial em muitos idiomas, mas poderá ser divertido em alguns outros.
Jonathan Allan
3
Você pode editar a pergunta para incluir o que constitui uma estrutura binária válida? Talvez uma definição como a tree is an object that contains a value and either two other trees or pointers to them. Uma definição que inclua idiomas sem objetos também seria boa.
Jo King

Respostas:

11

Gelatina , 3 bytes

ŒḊ’

Um link monádico que aceita uma lista que representa a árvore:, [root_value, left_tree, right_tree]onde cada uma left_treee right_treesão estruturas semelhantes (vazias, se necessário), que produzem a altura.

Experimente online!

Quão?

Bastante trivial em Jelly:

ŒḊ’ - Link: list, as described above
ŒḊ  - depth
  ’ - decremented (since leaves are `[value, [], []]`)
Jonathan Allan
fonte
Jonathon Allen, essa é uma linguagem interessante que você está usando. Como recém-chegado, você pode fornecer um link ou uma referência de site que ensine as pessoas a usar o Jelly?
T. Salim
4
Clique no link no cabeçalho - é uma linguagem de golfe desenvolvida por Dennis , um dos moderadores do site.
Jonathan Allan
2
Eu me pergunto o quão controverso seria representar uma folha em xvez de [x, [], []]...
Erik the Outgolfer
@EriktheOutgolfer Para acompanhar a natureza "ponteiro" e "estrutura" da pergunta, acho que todos os nós devem ter a mesma forma.
Jonathan Allan
10

Python 2 ,  35  33 bytes

Agradecimentos a Arnauld por perceber e supervisionar 4.

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

Uma função recursiva que aceita uma lista que representa a árvore:, [root_value, left_tree, right_tree]onde cada uma left_treee right_treesão estruturas semelhantes (vazias, se necessário), que retornam a altura.

Experimente online!

Observe que []retornará False, mas em Python False==0.

Jonathan Allan
fonte
A mesma pessoa pode dar duas respostas diferentes para a mesma pergunta?
T. Salim
6
Sim, é claro, o golfe é uma competição no nível do idioma. Às vezes, até uma segunda entrada no mesmo idioma é aceitável, se a abordagem for muito diferente.
Jonathan Allan
@ Arnauld Acho que sim (eu assumi que números não inteiros possam estar presentes por algum motivo)
Jonathan Allan
6

Haskell, 33 bytes

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

Usando o tipo de árvore customizada data T = L | N T T Int, que é o equivalente Haskell da estrutura C fornecida no desafio.

Experimente online!

nimi
fonte
6

Perl 6 , 25 bytes

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

Entrada é uma lista de 3 elementos (l, r, v). A árvore vazia é a lista vazia.

Experimente online!

Explicação

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

Solução antiga, 30 bytes

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

Experimente online!

Nwellnhof
fonte
O &?BLOCKtruque é interessante, mas são alguns bytes mais curtos para atribuir o bloco a $!
Jo King
@ JoKing Eu não sei. Armazenar a solução de desafio em um mundo volátil como $!ou $/parece trapaça para mim.
nwellnhof
(Ab) usando variáveis ​​como $! e $ / é uma prática bastante comum no golfe P6.
user0721090601
6

05AB1E , 11 7 5 bytes

Δ€`}N

-4 bytes graças a @ExpiredData .
-2 bytes graças a @Grimy .

O formato de entrada é semelhante ao da resposta Jelly: uma lista que representa a árvore:, [root_value, left_tree, right_tree]onde cada uma left_treee right_treesão estruturas semelhantes (opcionalmente vazias). Ou seja, [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]representa a árvore a partir da descrição do desafio.

Experimente online ou verifique mais alguns casos de teste .

Explicação:

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

Observe que, embora 05AB1E seja baseado em 0, o loop de alterações Δfaz com que o índice de saída esteja correto, pois precisa de uma iteração adicional para verificar se não muda mais.

Kevin Cruijssen
fonte
1
7 bytes?
Dados expirados
@ExpiredData Ah, claro .. Obrigado! :)
Kevin Cruijssen
1
5 bytes
Grimmy
@ Grimy Eu pensei que usar o índice fora de um loop só funcionava no código legado ..: S Obrigado!
Kevin Cruijssen 19/08
5

JavaScript (ES6),  35  33 bytes

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

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

Experimente online!

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
fonte
Parece que você pode salvar um byte a&&-~.
Shaggy
1
@ Shagy Isso levaria a comparações com indefinido .
Arnauld
4

C, 43 bytes

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

Estrutura da árvore binária é a seguinte:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;
T. Salim
fonte
2
55 bytes Experimente online! Alguns truques de golfe específicos para C estão aqui!
ErikF
1
@ErikF ou 45 bytes
Arnauld
2
43 bytes
nwellnhof
3
Se o seu envio depender de sinalizadores, você pode adicioná-los ao cabeçalho do seu envio?
Jo King
1
Edifício @nwellnhof 42 bytes
ceilingcat
4

JavaScript (Node.js) , 32 bytes

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

Experimente online!

Usar o nome em flatvez de flattenou smooshé uma ótima idéia para o código de golfe.

Usando []para nó nulo na árvore e [left, right, value]para nós. valueaqui é um número inteiro.

tsh
fonte
3

Haskell, 28 bytes

Usando a seguinte definição de dados:

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

A altura é:

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

Esquema, 72 bytes

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

Versão mais legível:

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

Usando listas do formulário (dados, esquerda, direita) para representar uma árvore. Por exemplo

   1
  / \
  2  3
 /\
 4 5

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

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

Experimente Online!

Zachary Cotton
fonte
2

R , 51 bytes

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

Experimente online!

  • Entrada: uma lista aninhada no formato:list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

  • Algoritmo: Nivela a árvore iterativamente em um nível até que se torne um vetor plano: a contagem de iterações corresponde à profundidade máxima.

Inspirado na solução @KevinCruijssen


Alternativa recursiva:

R , 64 bytes

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

Experimente online!

Redefine a função / operador, '~'permitindo calcular a profundidade máxima de uma árvore armazenada em uma estrutura de lista.

A estrutura da lista de uma árvore está no formato: list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

  • -2 graças a @Giuseppe
digEmAll
fonte
por que você usa d=1e depois d-1no final? Você não poderia começar em 0?
Giuseppe
Também mudei >para ~ aqui para que os casos de teste sejam mais fáceis de inserir
Giuseppe
@ Giuseppe: claro ... eu estava perdendo o óbvio 🤦‍♂️
digEmAll
1

K (ngn / k) , 4 bytes

Solução:

#,/\

Experimente online!

Explicação:

Eu acho que posso ter entendido errado.

Representando uma árvore como a lista de 3 itens (nó pai; filho esquerdo; filho direito), o exemplo pode ser representado como

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

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

Portanto, a solução é achatar iterativamente e contar as iterações:

#,/\ / the solution
   \ / iterate
 ,/  / flatten
#    / count
rua
fonte
0

Carvão , 29 bytes

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

Experimente online! Link é a versão detalhada do código. Modifica temporariamente a árvore durante o processamento. Explicação:

⊞θ⁰

Empurre zero para o nó raiz.

⊞υθ

Envie o nó raiz para a lista de todos os nós.

Fυ«

Faça uma pesquisa pela primeira vez da árvore.

≔⊕⊟ιθ

Obtenha a profundidade desse nó.

FΦι∧κλ

Faça um loop sobre qualquer nó filho.

⊞υ⊞Oκθ

Diga ao nó filho a profundidade do pai e envie-o para a lista de todos os nós.

»Iθ

Uma vez percorridos todos os nós, imprima a profundidade do último nó. Como a travessia foi a primeira da largura, essa será a altura da árvore.

Neil
fonte
0

Stax , 5 bytes

▐▌µ╡⌂

Execute e depure

Stax não tem ponteiros nem valores nulos, então eu represento a entrada como [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]. Talvez seja uma vantagem injusta, mas foi a mais próxima que pude chegar.

Descompactado, não jogado e comentado, o código fica assim.

        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

Execute este

recursivo
fonte
0

Kotlin, 45 bytes

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

Supondo que a seguinte classe esteja definida

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

Experimente online

Aso Leo
fonte
0

Julia, 27 bytes

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

Com a seguinte estrutura representando a árvore binária:

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

cé uma tupla que representa os nós esquerdo e direito e a tupla vazia ()é usada para sinalizar a ausência de um nó.

user3263164
fonte
0

Kotlin , 42 bytes

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

Experimente online!

Onde

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