Java的算法寻找独立的节点上最大的集二叉树 [英] Java Algorithm for finding the largest set of independent nodes in a binary tree

问题描述

由独立的节点，我的意思是返回集不能包含在直接关系，父母与子女不能同时被列入的节点。我试图用谷歌，但没有成功。我不认为我有权利搜索词。

By independent nodes, I mean that the returned set can not contain nodes that are in immediate relations, parent and child cannot both be included. I tried to use Google, with no success. I don't think I have the right search words.

有一个环节，任何帮助将非常AP preciated。刚开始在这现在。

A link, any help would be very much appreciated. Just started on this now.

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

I need to return the actual set of independent nodes, not just the amount.

推荐答案

您可以计算与动态规划（记忆化）这个递归函数：

You can compute this recursive function with dynamic programming (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])      })

我们的想法是，你可以选择一个节点，或者选择不接它。如果你选择，你不能选择它的直接的孩子，但你可以选择从孙子的最大集。如果你不接话，你可以选择最大设定从直接孩子。

The idea is, you can pick a node or choose not to pick it. If you pick it, you can't pick its direct children but you can pick the maximum set from its grandchildren. If you don't pick it, you can pick maximum set from the direct children.

如果你需要设定本身，你只需要保存你如何选择最大为每个节点。这是类似于 LCS算法。

If you need the set itself, you just have to store how you selected "Max" for each node. It's similar to the LCS algorithm.

这个算法为O（n）。它适用于一般的，不只是二进制树的树。

This algorithm is O(n). It works on trees in general, not just binary trees.

这篇关于Java的算法寻找独立的节点上最大的集二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！