1

我有一个像这样的树结构：

public class Project {
    private String id;
    private String description;
    private List<Project> subProjects;
    private List<Document> documents;
}

List<Project> projects = new ArrayList<Project>;

项目可以有子项目或文档，但不能同时有。我的问题是尝试通过从中删除每个没有文档的项目或子项目来过滤此列表。因此，如果项目没有文档且没有子项目，或者如果他的子项目都没有文档，我们将删除该项目。

可以递归完成吗？

4

2 回答 2

1

如果你能保证树形结构，即没有循环，你所需要的只是一个简单的后序 DFS。

如果您不想修改您的Project类，请在过滤器函数中创建一个 HashMap，（键：项目，值：它的子树中的总文档。）

现在，map[P] = sum of all map[child] + number of documents in P当孩子在 P 的子项目变量中时。

就是这样，甚至不需要边缘条件检查。它应该适用于 P 下的任意数量的子项目或文档，包括您的条件，其中一个必须为 0。

于 2017-10-19T14:54:17.887 回答
1

直接解释您的条件A. remove if subProjects and documents are empty或B. all children have no documents （假设“他的子项目都没有文件”是指所有孩子，而不仅仅是直接孩子）

定义一个布尔函数通常有助于检查节点的状态，然后可以查询它以检查是否应该删除节点

该代码假定您将其放入Project，如果您不是，则需要将其作为参数传递

boolean isEmpty()
{
    return subProjects.isEmpty() && documents.isEmpty();
}

boolean isChildrenEmpty()
{
    //put before the recursion for speed
    if(!documents.isEmpty()) //check if self has documents
        return false;

    for(Project child : subProjects)
        if(!child.isChildrenEmpty()) //check if any child has documents
            return false;

    return true; //all children + self have no documents
}

boolean toRemove()
{
    if(isEmpty()) //no children, no documents
        return true;

    for(Project child : subProjects)
        if(!child.isChildrenEmpty()) //a child has a document
            return false;
    return true;
}
于 2017-10-19T15:30:12.287 回答