Да, он всегда будет выдавать константное значение, а именно 0
. Нужно заменить строчку return Math.max(left, right);
на return Math.max(left, right) + 1;
. Исправленный вариант:
static class Node {
Node left;
Node right;
static int height(Node node) {
if (node == null) {
return 0;
}
int left = height(node.left);
int right = height(node.right);
return Math.max(left, right) + 1;
}
}
Хочу заметить, что этот метод вычисляет не ширину дерева, а высоту, то есть расстояние от корня до самого глубокого листа. Если вы хотите вычислять не высоту, а ширину дерева, то сначала стоит определить, что такое ширина дерева. Например, можно определить её как максимальная ширина уровня дерева
, где ширина уровня дерева
есть число вершин, находящихся на некотором уровне, то есть на одинаковом расстоянии от корня. Тогда алгоритм вычисления ширины дерева выглядит следующим образом:
- Найдём глубину дерева уже написанным методом. Обозначим её за
h
.
- Всего уровней в дереве ровно
h + 1
. Заведём массив на h + 1
элементов, в i
-ой его ячейке будет записано число вершин на i
-ом уровне. Изначально массив заполнен нулями.
- Обойдём дерево любым алгоритмом, в процессе увеличивая соответствующие ячейки массива.
- По нашему определению ширина дерева равна максимуму элементов в этом массиве.
Собственно, код:
static class Node {
Node left;
Node right;
static int height(Node node) {
if (node == null) {
return 0;
}
int left = height(node.left);
int right = height(node.right);
return Math.max(left, right) + 1;
}
static void dfs(Node node, int nodeHeight, int[] numberVertexesOnLevels) {
++numberVertexesOnLevels[nodeHeight];
dfs(node.left, nodeHeight + 1, numberVertexesOnLevels);
dfs(node.right, nodeHeight + 1, numberVertexesOnLevels);
}
static int width(Node node) {
int height = height(node);
int[] numberVertexesOnLevels = new int[height];
dfs(node, 0, numberVertexesOnLevels);
return Arrays.stream(numberVertexesOnLevels).max().getAsInt();
}
}