Задачник по алгоритмам

Программа курса:

Задача 17: Максимальная глубина N-арного дерева

Условие задачи

Напишите определение функции maxDepth(root: Node) -> int, которая принимает корень n-арного дерева (root) и возвращает его максимальную глубину.

!Важно:
Если корня нет, глубина равна 0
Если у узла нет детей, глубина равна 1

Максимальная глубина — это количество узлов на самом длинном пути от корневого узла до самого дальнего листового узла.

Формат ввода:

  • Дерево задается(скрытно в вашем коде) в виде уровня (level order traversal), где каждый список дочерних узлов разделяется значением null.

Пример реализации узла дерева:

class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

Этот класс используется для создания n-арного дерева. Каждый узел имеет значение (val) и список дочерних узлов (children).

Примеры:

Пример 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3

Explanation:
    Дерево выглядит так:
           1
        /  |  \
       3   2   4
      / \
     5   6

Максимальная глубина дерева: 3.

Пример 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: 5

Explanation:
    Дерево выглядит так:
                   1
               /   |   |   \
             2     3   4    5
                  / \        |
                 6   7       8
                      \       \
                       9       10
                      /         \
                    11           12
                   /              \
                 13                14

Максимальная глубина дерева: 5.

0
Вы должны Войти или Зарегистрироваться чтобы оставлять комментарии