Высота бинарного дерева - это расстояние от корневого узла до дочернего узла, который находится дальше всего от корня.

Ниже приведен пример:

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

Высота бинарного дерева: 4

Определение двоичного дерева

Дерево - это объект, который содержит целочисленное значение со знаком и два других дерева или указатели на них.

Структура структуры двоичного дерева выглядит примерно так:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;

Соревнование:

вход

Корень бинарного дерева

Выход

Число, представляющее высоту двоичного дерева

Предполагая, что вам дан корень двоичного дерева в качестве входных данных, напишите самую короткую программу, которая вычисляет высоту двоичного дерева и возвращает высоту. Программа с наименьшим количеством байтов (учет пробелов) выигрывает.

Желе , 3 байта

ŒḊ’

Монадическая ссылка, принимающая список, представляющий дерево:, [root_value, left_tree, right_tree]где каждая из left_treeи right_treeявляется похожими структурами (пустые, если необходимо), которая возвращает высоту.

Попробуйте онлайн!

Как?

Довольно тривиально в желе:

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

Python 2 ,  35  33 байта

Спасибо Арно за то, что он заметил недосмотр и спасение 4.

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

Рекурсивная функция, принимающая список, представляющий дерево:, [root_value, left_tree, right_tree]где каждая из left_treeи right_treeявляется похожей структурой (пустой, если необходимо), которая возвращает высоту.

Попробуйте онлайн!

^{Обратите внимание, что []вернется False, но в Python False==0.}

Haskell, 33 байта

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

Использование пользовательского типа дерева data T = L | N T T Int, который является эквивалентом языка Haskell структуры C, указанной в задании.

Попробуйте онлайн!

Perl 6 , 25 байт

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

Ввод 3-элементный список (l, r, v). Пустое дерево - это пустой список.

Попробуйте онлайн!

объяснение

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

Старое решение, 30 байт

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

Попробуйте онлайн!

05AB1E , 11 7 5 байт

Δ€`}N

-4 байта благодаря @ExpiredData .
-2 байта благодаря @Grimy .

Формат ввода аналогичен ответу Jelly: список, представляющий дерево:, [root_value, left_tree, right_tree]где каждая из left_treeи right_treeпредставляет собой схожие структуры (необязательно пустые). Т.е. [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]представляет дерево из описания вызова.

Попробуйте онлайн или проверьте еще несколько тестов .

Объяснение:

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

Обратите внимание, что хотя 05AB1E основано на 0, цикл изменений Δприводит к корректности выходного индекса, поскольку ему требуется дополнительная итерация для проверки того, что он больше не изменяется.

JavaScript (ES6),  35  33 байта

Структура ввода: [[left_node], [right_node], value]

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

Попробуйте онлайн!

комментарии

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 байта

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

Структура бинарного дерева следующая:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;

JavaScript (Node.js) , 32 байта

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

Попробуйте онлайн!

Используя имя flatвместо flattenилиsmoosh является отличной идеей для кода гольф.

Используется []для нулевого узла в дереве и [left, right, value]для узлов. valueздесь целое число

Wolfram Language (Mathematica) , 10 байт

Depth@#-2&

Попробуйте онлайн! Принимает ввод как вложенный список {v, l, r}.

Haskell, 28 байт

Используя следующее определение данных:

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

Высота составляет:

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

Схема, 72 байта

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

Более читаемая версия:

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

Использование списков формы (данные, слева, справа) для представления дерева. Например

   1
  / \
  2  3
 /\
 4 5

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

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

Попробуйте онлайн!

R , 51 байт

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

Попробуйте онлайн!

• Входные данные: вложенный список в формате:list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

• Алгоритм: итеративно выравнивает дерево на один уровень, пока оно не станет плоским вектором: количество итераций соответствует максимальной глубине.

Вдохновленный решением @KevinCruijssen

Рекурсивная альтернатива:

R , 64 байта

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

Попробуйте онлайн!

Переопределяет функцию / оператор, '~'позволяя вычислить максимальную глубину дерева, хранящегося в структуре списка.

Структура списка дерева имеет формат: list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

• -2 благодаря @Giuseppe

Japt , 8 байт

@eU=c1}a

Попытайся

Оригинал, 9 байт

Ω¡ÒßXÃrw

Попытайся

К (нгн / к) , 4 байта

Решение:

#,/\

Попробуйте онлайн!

Объяснение:

Я думаю, что, возможно, упустил момент.

Представляя дерево в виде списка из 3 элементов (parent-node; left-child; right-child), пример может быть представлен как

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

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

Таким образом, решение состоит в том, чтобы итеративно сгладить и посчитать итерации:

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

Древесный уголь , 29 байт

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

Попробуйте онлайн! Ссылка на подробную версию кода. Временно изменяет дерево во время обработки. Объяснение:

⊞θ⁰

Нажмите ноль в корневой узел.

⊞υθ

Нажмите корневой узел в список всех узлов.

Ｆυ«

Выполните поиск дерева в ширину.

≔⊕⊟ιθ

Получите глубину этого узла.

ＦΦι∧κλ

Цикл по любым дочерним узлам.

⊞υ⊞Ｏκθ

Сообщите дочернему узлу глубину его родителя и поместите его в список всех узлов.

»Ｉθ

Когда все узлы пройдены, выведите глубину последнего узла. Поскольку обход был в ширину, это будет высота дерева.

Stax , 5 байт

▐▌µ╡⌂

Запустите и отладьте его

Stax не имеет ни указателей, ни нулевых значений, поэтому я представляю ввод как [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]. Может быть, это несправедливое преимущество, но это было самое близкое, что я мог получить.

Распакованный, распакованный и прокомментированный код выглядит следующим образом.

        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

Запустите этот

Котлин, 45 байт

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

Предполагая, что следующий класс определен

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

Попробуйте онлайн

Юлия, 27 байт

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

Со следующей структурой, представляющей двоичное дерево:

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

cявляется кортежем, представляющим левый и правый узлы, и пустой кортеж ()используется, чтобы сигнализировать об отсутствии узла.

Котлин , 42 байта

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

Попробуйте онлайн!

где

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