Для древовидной структуры следующим образом

public class Node implements Comparable<Node> {
    private List<Node> nodes=new ArrayList<Node>();
    private String name="";
    private List<String> leaves=new ArrayList<String>();
    private Node parent=null;

    public List<Node> getNodes() {
        return nodes;
    }

    public void setNodes(List<Node> nodes) {
        this.nodes = nodes;
    }

    public List<String> getLeaves() {
        return leaves;
    }

    public void setLeaves(List<String> leaves) {
        this.leaves = leaves;
    }

    @Override
    public int compareTo(Node o) {
        return this.getName().compareTo(o.getName());
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node getParent() {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    public int getDepth() {
        int depth = 0;
        Node parent = this.getParent();
        while (parent != null) {
            depth++;
            parent = parent.getParent();
        }
        return depth;
    }
}

От узла я хочу иметь метод, который возвращает все различные прямые и косвенные листья (в приведенном выше случае строкиleaves  будет листьями), для этого узла в отсортированном порядке.

Выше этоhighly Разрушенная структура данных облегчает тестирование и демонстрацию. Я попробовал следующие 3 подхода,

Подход А Очень медленно, когда глубина велика ~ 20, так как самые глубокие листья пересекаются несколько раз, по одному разу для каждого из его предков, следовательно, один и тот же путь пересекается несколько раз.

    public List<String> getLeavesDeep1() {
        Set<String> leaves = new TreeSet<String>();
        leaves.addAll(getLeaves());
        for (Node node : getNodes()) {
            leaves.addAll(node.getLeavesDeep1());
        }
        return new ArrayList<String>(leaves);
    }

Avg: 12694 мс / без сортировки / отчет & gt; Avg: 471 мс

Подход Б Немного быстрее, чем A, так как число узлов сравнительно очень меньше, чем уходит, поэтому, используя подход A, но для узлов, а затем для каждого из узлов, получая только прямые листья.

    private List<Node> getNodesDeep2() {
        Set<Node> nodes = new TreeSet<Node>();
        nodes.addAll(getNodes());
        for (Node node : getNodes()) {
            nodes.addAll(node.getNodesDeep2());
        }
        return new ArrayList<Node>(nodes);
    }

    public List<String> getLeavesDeep2() {
        Set<String> leaves = new TreeSet<String>();
        leaves.addAll(getLeaves());
        for (Node node : getNodesDeep2()) {
            leaves.addAll(node.getLeaves());
        }
        return new ArrayList<String>(leaves);
    }

Avg: 4355 мс / без сортировки / отчет & gt; Avg: 2406 мс

Подход С Избегайте TreeSet, использовать ArrayList & sorted & amp; отфильтрованный (не лучший способ сортировки / отличия) перед возвратом

    private List<Node> getNodesDeep3() {
        List<Node> nodes = new ArrayList<Node>();
        nodes.addAll(getNodes());
        for (Node node : getNodes()) {
            nodes.addAll(node.getNodesDeep3());
        }
        return new ArrayList<Node>(new TreeSet<Node>(nodes));
    }

    public List<String> getLeavesDeep3() {
        List<String> leaves = new ArrayList<String>();
        leaves.addAll(getLeaves());
        for (Node node : getNodesDeep3()) {
            leaves.addAll(node.getLeaves());
        }
        return new ArrayList<String>(new TreeSet<String>(leaves));
    }

Avg: 4400

В поисках чего-то более быстрого, я знаю, что есть определенные обходы деревьев, которые можно использовать, но я бы предпочел что-то более простое, если оно существует.P.S. These is no use case for searching at the moment, В моем реальном классе времена намного выше примерно в 3 раза по сравнению с вышеупомянутыми случаями, так как структура намного более сложна с листьями, не являющимися простыми строками, а POJO

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

private static final int NODES = 5;
private static final int LEAVES = 25;
private static final int DEPTH = 8;

public void addChildren(Node parent) {
    List<Node> nodes = new ArrayList<Node>();
    List<String> leaves = new ArrayList<String>();
    for (int i = 0; i < LEAVES; i++) {
        leaves.add(String.format("%s_leaf_%s", parent.getName(), i));
    }
    for (int i = 0; i < NODES; i++) {
        Node child = new Node();
        child.setParent(parent);
        child.setName(String.format("%s_%s", parent.getName(), i));
        nodes.add(child);
        if (child.getDepth() < DEPTH) {
            addChildren(child);
        }
    }
    parent.setNodes(nodes);
    parent.setLeaves(leaves);
}

@Test
public void testCase() {
    long start, tot=0;
    long t = 0;
    List<String> leaves;
    Node target = new Node();
    target.setName("Root");
    addChildren(target);
    for (int i = 0; i < 10; i++) {
        start = System.currentTimeMillis();
        leaves = target.getLeavesDeep5();
        t = System.currentTimeMillis() - start;
        tot += t;
        System.out.println(leaves.size() + " " + t);
    }

    System.out.println("Avg: " + (tot / 10));
}

Приемлемы ответы на любом языке, включая псевдокод, если только он не связывает решение с этим языком (Exception: Pure java code is barred from the second clause)