Para uma estrutura de árvore da seguinte forma

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

De um nó, desejo ter um método que retorne todas as folhas diretas e indiretas distintas (no caso acima, as stringsleaves seriam as folhas), para esse nó na ordem de classificação.

Acima é umaltamente Derrubada estrutura de dados para fácil teste e demonstração. Eu tentei as seguintes 3 abordagens,

Aproximação A Muito lenta quando a profundidade é grande ~ 20, uma vez que as folhas mais profundas são percorridas várias vezes, uma vez para cada um de seus ancestrais, portanto o mesmo caminho é percorrido várias vezes.

    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 ms / Sem classificação / distinto> Avg: 471 ms

Abordagem B Pouco mais rápido que A, já que o número de nós é comparativamente muito menor do que as folhas, portanto, usando a abordagem A, mas para os nós e, em seguida, para cada um dos nós, obtendo somente as folhas diretas.

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

Média: 4355 ms / Sem classificação / distinto> Média: 2406 ms

Abordagem C Evite o TreeSet, use o ArrayList e classifique e filtre (não é a melhor maneira de classificar / distinto) antes de retornar

    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

Procurando por algo mais rápido, eu sei que existem certas travessias de árvore que podem ser usadas, mas eu preferiria algo mais simples se existir.P.S. Estes não são casos de uso para procurar no momento. Na minha classe real os tempos são muito mais altos, aproximadamente 3x para os casos acima, já que a estrutura é muito mais complexa, com as folhas não sendo simples, mas POJOs

A seguir está o teste que usei para obter os horários

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

As respostas em qualquer idioma são aceitáveis, incluindo pseudo-código, desde que não vinculem firmemente a solução a esse idioma (Exceção: o código java puro é barrado da segunda cláusula)