У меня возникли проблемы с проблемой, связанной с деревом каталогов и поиском наименьшего и наибольшего пути длины в этом дереве. Проблема в следующем:
Учитывая строку имен каталогов и файлов, где число «-» указывает на связь между всеми каталогами (например, какие файлы и каталоги находятся в каталоге), найдите наименьшую и наибольшую длину пути.
Например, строка со следующим содержимым:
dir1
-file1
-file2
-innerDir1
--file11
--file12
--file13
--innerinnerDir1
---file111
-innerDir2
--file21
показывает, что file1, file2, innderDir1 и innderDir2 находятся в каталоге dir1. file11, file12, file13 и innerinnerDir1 находятся в каталоге innerDir1.
Путь к файлу "dir1/" явно является кратчайшим путем, где "dir1/innerDir1/innerinnerDir1/file111" явно является самым длинным путем (измеряемым по длине строки).
Из моей работы я понимаю, что это проблема дерева, в частности, проблема дерева каталогов. Итак, я пробовал 2 рекурсивных метода: один находит максимум, другой находит минимум.
Однако я не могу понять, как это сделать. Наличие «-» определяет, какие каталоги/файлы находятся в каких каталогах, что меня смущает. У меня также реализована базовая древовидная структура (см. код ниже). Как я могу построить дерево по строке? Должен ли я не беспокоиться о построении дерева, а затем обходить его, а вместо этого просто попытаться найти минимум и максимум без использования структуры дерева?
Код дерева:
public class Tree<T> {
private Node<T> root;
public Tree(T rootData) {
root = new Node<T>();
root.data = rootData;
root.children = new ArrayList<Node<T>>();
}
public static class Node<T> {
private T data;
private Node<T> parent;
private List<Node<T>> children;
}
}
