独立节点,我的意思是返回的集合不能包含有直接关系的节点,不能同时包含父节点和子节点。我尝试使用谷歌,但没有成功。我不认为我有正确的搜索词。
一个链接,任何帮助将不胜感激。现在才开始做这件事。
我需要返回独立节点的实际集合,而不仅仅是数量。
最佳答案
您可以使用动态规划(记忆化)计算此递归函数:
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]) })
想法是,您可以选择一个节点或选择不选择它。如果你挑选它,你不能挑选它的直接 child ,但你可以从它的孙辈中挑选最大的集合。如果您不选择它,您可以从直接 child 中选择最大集合。
如果您需要集合本身,您只需存储您为每个节点选择“Max”的方式。它类似于 LCS algorithm .
这个算法是O(n)。它适用于一般的树,而不仅仅是二叉树。
关于用于查找二叉树中最大独立节点集的 Java 算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1567532/