java - 用于在二叉树中查找最大独立节点集的 Java 算法

Question

通过独立节点，我的意思是返回的集合不能包含直接关系的节点，不能同时包含父节点和子节点。我尝试使用谷歌，但没有成功。我认为我没有正确的搜索词。

一个链接，任何帮助将不胜感激。现在才开始做这个。

我需要返回实际的独立节点集，而不仅仅是数量。

Answer 1

您可以使用动态编程（记忆）计算此递归函数：

MaxSet(node) = 1 if "node" is a leaf
MaxSet(node) = Max(1 + Sum{ i=0..3: MaxSet(node.Grandchildren[i]) },  
                       Sum{ i=0..1: MaxSet(node.Children[i])      })

这个想法是，您可以选择一个节点或选择不选择它。如果选择它，则不能选择其直系子代，但可以从其孙代中选择最大集。如果你不选择它，你可以从直接孩子那里选择最大集。

如果您需要集合本身，您只需存储如何为每个节点选择“Max”。它类似于LCS 算法。

这个算法是 O(n)。它通常适用于树，而不仅仅是二叉树。

Answer 2

我会先取出所有叶子，同时将它们的父母标记为不取，然后删除所有标记的叶子，直到没有留下这样的叶子，然后递归直到树为空。我没有证据证明这总是产生最大可能的集合，但我相信它应该。

Answer 3

我已经为同一个问题提供了一个问题的答案，虽然解决方案是在 python 中，但解释、算法和测试用例可能是适用的。