Пытался реализовать метод нахождения высоты в дереве, но ничего не получается
public final class Department {
public final String name;
public final List<Department> subDepartments;
public Department(String name) {
this.name = name;
this.subDepartments = new ArrayList<>();
}
public Department(String name, Department... departments) {
this.name = name;
this.subDepartments = Arrays.asList(departments);
}
public String getName() {
return name;
}
public List<Department> getSubDepartments() {
return subDepartments;
}
}
public final class DepartmentMaxDepth {
Integer height = 0;
private DepartmentMaxDepth() {
}
public static Integer calculateMaxDepth(Department rootDepartment) {
Integer height = 0;
if (rootDepartment.equals(null)) {
return 0;
}
else {
if(rootDepartment.getSubDepartments() != null) {
if (rootDepartment.getSubDepartments().size() == 0) {
return height;
} else {
for (int i = 0; i < rootDepartment.subDepartments.size(); i++) {
height = Math.max(height, this.calculateMaxDepth(rootDepartment.subDepartments.get(i)));
}
return height + 1;
}
}
else {
return height;
}
}
}
}
Также есть тесты, которые должны проходить через код class
MaxTreeDepthTest {
public static final String TASK = "department";
static Department constructExample() {
return new Department("A", new Department("B", new Department("D")), new Department("C"));
}
static Department constructExampleWithNull() {
return new Department("A", null, new Department("B", new Department("D")), null, new Department("C"));
}
static Department constructWithNullLevel() {
return new Department("A", new Department("B", null, null, null, null),
new Department("C", null, null, null, null), new Department("D"));
}
@Test
@DisplayName("Should be zero on null")
void testOnNull() {
assertEquals(0, DepartmentMaxDepth.calculateMaxDepth(null), "Depth is 0 on null root");
}
@Test
@DisplayName("Should handle basic cases")
void testBasic() {
assertEquals(1, DepartmentMaxDepth.calculateMaxDepth(new Department("Chief dept")),
"Depth should be 1 when root is leaf");
assertEquals(3, DepartmentMaxDepth.calculateMaxDepth(constructExample()), "Should handle example");
assertEquals(3, DepartmentMaxDepth.calculateMaxDepth(constructExampleWithNull()),
"Should handle example with null");
assertEquals(2, DepartmentMaxDepth.calculateMaxDepth(constructWithNullLevel()),
"Should handle null children correctly");
}
}
И полное описание задания: Структура отделов представлена в виде дерева. Необходимо написать функцию, способную находить максимальный путь от корня до листков. Согласно решению руководства, отделы занимающиеся [ДАННЫЕ УДАЛЕНЫ] не должны отображаться в программе и в иерархии будут представлены с помощью null, нужно это учесть. Помимо этого, необходимо учесть, что иерархии могут быть очень длинными - более 10000 отделов. Поэтому хоть рекурсивное решение подойдет, необходимо найти способ избежать переполнения стека. Теперь пара примеров:
A
/ \
B C
\
D
глубина равна 3, самый длинный путь от корня до листка: A - B - D. В дереве
A самый длинный путь от корня до листка: A, соответственно глубина дерева равна 1.
Поскольку скрытые отделы не учитываются в иерархии, то длина дерева вида
A
/ \
null null
равна 1, а не 2
Ответы (1 шт):
Немного подправил ваш метод, все тесты зеленые.
public static Integer calculateMaxDepth(Department rootDepartment) {
int height = 0;
if (rootDepartment == null) {
return 0;
}
else {
if(rootDepartment.getSubDepartments() != null) {
if (rootDepartment.getSubDepartments().size() != 0) {
for (int i = 0; i < rootDepartment.subDepartments.size(); i++) {
height = Math.max(height, calculateMaxDepth(rootDepartment.subDepartments.get(i)));
}
}
return height + 1;
}
else {
return height;
}
}
}
На больших данных, думаю, сами проверите переполнение стека...