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

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

一个链接，任何帮助将非常感谢。 刚刚开始这个。

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

Answer 1

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

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

这个想法是，你可以选择一个节点或选择不选择它。 如果你选择它，你不能选择它的直接孩子，但你可以从其孙子中选择最大的一组。 如果您不选择它，您可以从直接儿童中挑选最大值。

如果您需要设置本身，则只需存储为每个节点选择“最大”的方式。 它类似于LCS算法 。

该算法是O（n）。 它一般适用于树木，而不仅仅是二叉树。

Answer 2

我会先取下所有的叶子，同时将它们的父母标记为不采取，然后移除所有标记的叶子，直到没有留下这些叶子，然后递归直到树为空。 我没有certificate这总是产生最大可能的设置，但我相信它应该。

Answer 3

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