Задачка на алгоритмы
Всем привет. Решил разобрать пример похожей задачи которая не позволила мне пройти следующий этап собеса в Яндекс и методику решения подобных задач. Т.к. поняв методику можно в целом решить любую подобного рода задачу.
Итак мне досталась задача на обход графа, а если быть точнее дерева.
Дан корень root двоичного дерева, верните его максимальную глубину. Максимальная глубина двоичного дерева - это количество узлов в самом длинном пути от корневого узла до самого дальнего листового узла.
Подобного рода задачи можно решить либо итеративно либо рекурсивно. Я выбрал рекурсию вспомнил что есть такой алгоритм dfs поиск в глубину. Чтобы решать такие задачи нужно вообще знать что такое рекурсия, база рекурсии, и когда собственно вызывать эту самую рекурсию. Рекурсия - это метод решения задачи, при котором функция вызывает саму себя для решения подзадачи того же типа. База рекурсии - это условие выхода из функции. Объясню на каноническом примере с факториалом
fun factorial(n: Int): Long { // База рекурсии if (n <= 1) { return 1 } // Рекурсивный случай - функция вызывает саму себя return n * factorial(n - 1) }
Итак нам нужно вернуть максимальную глубину двоичного дерева
class Solution { fun maxDepth(root: TreeNode?): Int { return dfs(root,0) }
fun dfs(root: TreeNode?, level: Int) : Int { // База рекурсии если root == null значит его родитель это листовой узел дерева. if(root == null) { return level }
//Запускаем рекурсию для левого и правого поддерева val leftLevel = dfs(root.left,level+1) val rightLevel = dfs(root.right,level+1)
//Возвращаем максимальный уровень return maxOf(leftLevel,rightLevel) } }
P.S. На собесе же в моем случае дерево было не двоичное и нужно было вернуть узел максимальной глубины.
