Нужно найти самые низкие узлы в дереве

Question

У меня есть список узлов, которые являются частью дерева.Я хочу отфильтровать список только для самых низких детей.Для дерева примеров:

(1)
 |
 +-- (2)
 |    
 +-- (3)
    |
    +-- (4)
    |  
    +-- (5)
         |
         +--(6)

Если мой список [1,2,5,6], я бы хотел, чтобы результаты были [2,6], потому что они являются самыми низкими потомками.

У меня есть метод узла is_descendant(), который принимает два узла и возвращает True или False.

Например:

1.is_descendant(2) ---> False
2.is_descendant(1) ---> True
6.is_descendant(1) ---> True

Моя первая идеяначинать с первого элемента в списке и применять метод is_descendant() ко всем другим элементам.Всякий раз, когда он возвращает True, я удаляю другой элемент из списка - поскольку это родительский узел.

Есть ли более эффективный способ сделать это?Или этот метод будет работать 100% времени (доказательство возможно?)

Answer 1

Правило выглядит так: если узел находится в списке, а любой из его потомков находится в списке, то узел следует удалить из списка.Это может быть реализовано с использованием довольно простой рекурсивной функции.

Некоторый Java-код для иллюстрации:

static <E> boolean descendentsIn(Node<E> node, Set<E> nodes)
{
  boolean descendentsIn = false;
  for(Node<E> n : node.children)
  {
    if(descendentsIn(n, nodes) || nodes.contains(n.e)) 
      descendentsIn = true;
  }
  if(descendentsIn && nodes.contains(node.e)) 
    nodes.remove(node.e);
  return descendentsIn;
}

static class Node<E>
{
  E e;
  List<Node<E>> children = new ArrayList<>();
  public Node(E e)
  {
    this.e = e;
  }
}

Тест:

public static void main(String[] args)
{
  Node<Integer> root = new Node<>(1);
  root.children.add(new Node<>(2));
  root.children.add(new Node<>(3));
  root.children.get(1).children.add(new Node<>(4));
  root.children.get(1).children.add(new Node<>(5));
  root.children.get(1).children.get(1).children.add(new Node<>(6));

  Set<Integer> nodes = new HashSet<>(Arrays.asList(1, 2, 5, 6));

  System.out.println("Before: " + nodes);
  descendentsIn(root, nodes);    
  System.out.println("After:  " + nodes);
}

Вывод:

Before: [1, 2, 5, 6]
After:  [2, 6]