Пытался реализовать метод нахождения высоты в дереве, но ничего не получается

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;
        }
    }
}

На больших данных, думаю, сами проверите переполнение стека...

→ Ссылка