需要找到树中最低的节点

规则似乎是,如果某个节点在列表中,并且其任何子节点都在列表中,则应将该节点从列表中删除。这可以使用相当简单的递归函数来实现。

一些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]