План курса / Все задачи / Алгоритмы и структуры данных
Максимальная глубина дерева
легко
Дан корень бинарного дерева. Нужно вернуть максимальное число вершин между корнем и одним из листов, включая в подсчет сам корень и лист
ВАЖНО: реализуй обход с использованием рекурсии
Пример 1:
Ввод: root = [1,2,3,4,5,null,6,null,null,7,8]
Вывод: 4
Объяснение: есть два наиболее длинных пути от корня до листа: 1 -> 2 -> 5 -> 7 и 1 -> 2 -> 5 -> 8 и каждый из них имеет длину 4
Пример 2:
Ввод: root = [8,null,4,null,null,9]
Вывод: 3
Ограничения:
Число узлов в дереве >= 1
Высота дерева <= 1000
Значение вершин дерева лежит в диапазоне [-10 000, 10 000] (включительно)
from tree_node import TreeNode
# class TreeNode:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def max_depth(root: Optional[TreeNode]) -> int:
if root is None:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
from tree_node import TreeNode
# class TreeNode:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def max_depth(root: Optional[TreeNode]) -> int:
if root is None:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
/**
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution
{
public static int MaxDepth(TreeNode root)
{
if (root == null)
{
return 0;
}
return 1 + Math.Max(MaxDepth(root.left), MaxDepth(root.right));
}
}
