需要在树中找到最低的节点
需要在树中找到最低的节点
提问于 2018-09-27 17:39:20
我有一个节点列表，这些节点是树的一部分。我只想把列表过滤给最低的孩子。对于示例树：
(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%的工作(证明是可能的？)
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-09-27 19:39:14
规则似乎是，如果一个节点在列表中，并且它的任何后代都在列表中，那么该节点应该从列表中删除。这可以使用一个相当简单的递归函数来实现。
一些用于稀释的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]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52542425
复制相关文章
相似问题
腾讯云开发者
