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

Question

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

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

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

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).它一般适用于树木,而不仅仅是二叉树.