Ссылка на leetcode: https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
Задача. Дано бинарное дерево. Найти его максимальную высоту.
Например, для дерева
Ответ 4.
Решение. Будем использовать in-order алгоритм обхода бинарного дерева (Алгоритмы обхода двоичного дерева):
public static void dfs(BinaryTree tree) {
if (tree == null) {
return;
}
visit(tree);
dfs(tree.left);
dfs(tree.right);
}
Вариант 1 решения. Будем высоту считать снизу вверх. Когда достигли листовой вершины (нет дочерних верших), то вернем ноль. Для каждой вершины будем находить максимальную глубину между левой и правой подветкой и прибавлять 1 к результату.
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
Изобразил на картинке, для нашего примера как будут происходить вычисления. Для каждой вершины нарисовал красным, какие значения будет возвращать функция:
Вариант 2. Считаем высоту сверху вниз, высоту передаем в качестве параметра функции. Сохраняем результат в глобальной переменной.
class Solution {
int max = 0;
public int maxDepth(TreeNode root) {
//Высота корня дерева = 1
traverse(root, 1);
return max;
}
private void traverse(TreeNode root, int height) {
if (root == null) {
return;
}
//обновляем максимум
max = Math.max(max, height);
//рекурсивный вызов для левой и правой вершины
traverse(root.left, height + 1);
traverse(root.right, height + 1);
}
}
Вариант 3. Считаем высоту сверху вниз, высоту передаем в качестве параметра функции. Вычисляем максимальную глубину между левой и правой подветкой и возвращаем результат в качестве возвращаемого значения функции.
class Solution {
public int maxDepth(TreeNode root) {
//Высота корня дерева = 1
return dfs(root, 1);
}
private int dfs(TreeNode root, int height) {
if (root == null) {
return height - 1;
}
//рекурсивный вызов для левой и правой вершины
int leftHeight = dfs(root.left, height + 1);
int rightHeight = dfs(root.right, height + 1);
return Math.max(leftHeight, rightHeight);
}
}
Top comments (0)