通过独立节点，我的意思是返回的集合不能包含具有直接关系的节点，父节点和子节点不能同时包含。我尝试使用谷歌，但没有成功。我认为我没有正确的搜索词。
一个链接，任何帮助将非常感激。现在才开始做这个。
我需要返回实际的独立节点集，而不仅仅是数量。
您可以使用动态编程（记忆）来计算此递归函数：
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)。它适用于一般的树，而不仅仅是二叉树。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
