Представление записываемой файловой системы с деревом

Question

У меня есть следующая задача в университете (см. Ниже), я сделал это решение.Но у меня есть две проблемы от моего учителя.

Я должен сделать это за O (n). Некоторые тесты не пройдены

Мой первый вопрос: как я могу сделать необходимые папки в O (n)??Во-вторых, в каких случаях это может сломаться?(Я не получаю никакой помощи от своего учителя ...)

Задание:

У нас есть структура папок, представленная простыми объектами, например:

class TreeItem{ 
  String name; 
  List<TreeItem> children; 
} 

Создайте функцию, которая получает два списка строк, один для пользовательских папок и один для

доступных для записи папок, и возвращает структуру папок, представленную в виде дерева, которая содержит все

доступные для записи папкиэто может быть достигнуто через хотя бы читаемую папку из корня.Дерево

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

).Папки, которые недоступны для записи, должны быть включены, если у них есть доступные для записи подпапки,

, но если у них нет доступного для записи потомка, их следует исключить, потому что это просто введет в заблуждение пользователя

(пытаясьнапример, выберите доступную для записи целевую папку.

public TreeItem getWritableFolderStructure(List<String> readableFolders, 
List<String> writableFolders){ 
  // TODO implement 
} 

• Папки всегда указываются с полными путями (например, / var / lib / jenkins)

• Пути в списке для записи, также в списке для чтения

Мой код следующий:

class TreeItem {
    public String name;
    public List<TreeItem> children;
    private boolean isVisited;

    public TreeItem() {
        this.children = new ArrayList<TreeItem>();
    }

    public TreeItem(String name) {
        this.name = name;
        this.children = new ArrayList<TreeItem>();
    }

    // we can add path with the depth-first search algorithm (modified)
    public void depthFirstSearchAdd(TreeItem t, String path) {
        for (int i = 0; i < t.children.size(); ++i) {
            if (!t.children.get(i).isVisited) {
                if (path.startsWith(t.children.get(i).name)
                        && path.split("/").length == t.children.get(i).name.split("/").length + 1) {
                    t.isVisited = true;
                    t.children.get(i).children.add(new TreeItem(path));
                    System.out.println("Added: " + path);
                    return;
                }
            }
            depthFirstSearchAdd(t.children.get(i), path);
        }
    }

    public TreeItem getWritableFolderStructure(List<String> readableFolders, List<String> writeableFolders) {
        List<String> neededFolders = new ArrayList<String>();
        // this part is an implementation of very "greedy" algorithm
        // if we split the path by "/" (according to the example, it is an linux like
        // file system) we get the folders which are in the path
        // if with the 'length' member we get the number of the folders in the path
        // se, if the writeable starts with the readable and the split length is 1
        // bigger -> the readable has an writeable folder
        // but if we have an '/' root the length is 0, so if the next
        for (String readable : readableFolders) {
            for (String writeable : writeableFolders) {
                if (readable.equals(writeable)) {
                    neededFolders.add(writeable);
                } else if (writeable.startsWith(readable)
                        && readable.split("/").length + 1 == writeable.split("/").length) {
                    neededFolders.add(writeable);
                    neededFolders.add(readable);
                } else if ("/".equals(readable) && writeable.startsWith(readable)
                        && readable.split("/").length + 2 == writeable.split("/").length) {
                    neededFolders.add(readable);
                } else {
                    neededFolders.add(writeable);
                }
            }
        }

        // make sure there aren't any duplication
        neededFolders = neededFolders.stream().distinct().collect(Collectors.toList());
        neededFolders.sort((str1, str2) -> str1.split("/").length - str2.split("/").length);
        // acording to the sort, the first element will be the root element

        String tempName = neededFolders.get(0);
        System.out.println("Added: " + tempName);
        neededFolders.remove(0);
        // get the children of the root
        int numOfFolders = ("/".equals(tempName)) ? tempName.split("/").length + 1 : tempName.split("/").length;
        List<String> tempChildren = neededFolders.stream()
                .filter((str) -> str.startsWith(tempName) && numOfFolders + 1 == str.split("/").length)
                .collect(Collectors.toList());
        this.name = tempName;
        // add the root children's
        for (int i = 0; i < tempChildren.size(); ++i) {
            System.out.println("Added: " + tempChildren.get(i));
            this.children.add(new TreeItem(tempChildren.get(i)));
        }
        neededFolders.removeAll(tempChildren);

        for (String str : neededFolders) {
            depthFirstSearchAdd(this, str);
        }

        return this;
    }
}