# Q：找到一个树的最大子集的节点受到一定的限制？

Given a Tree like the following:

``````            X
/               \
1               6
/   |   \       /   |   \
2   5   9       1   5   3
...             ...
``````

For each node there is a number(except for the root), in the example the numbers are random.

If a node is taken, the next child-node of this node cannot be taken. But the child-child-node is allowed to take. So it's just not okay to take following nodes.

I'm searching for an algorithm which constructs a subset of all nodes which is has maximum amount(the sum of numbers of all taken nodes). The root has to be taken.

I searched for solutions, I found the red-black-tree which is very similar but not really useful.

Any ideas on this?

``````            X
/               \
1               6
/   |   \       /   |   \
2   5   9       1   5   3
...             ...
``````

I'm searching for an algorithm which constructs a subset of all nodes which is has maximum amount(the sum of numbers of all taken nodes). The root has to be taken.

The problem you're trying to solve is called the maximum independent set problem applied to trees.

As a hint, think about the following:

• For each complete subtree of the tree, think about the optimal solution for that subtree in two cases - the case where you include that node in the solution, and the case where you exclude that node from the solution.

• Use dynamic programming: work from the leaves of the tree up to the root of the tree.

Hope this helps!

• 树的每一个完整的子树，子树，考虑最优解在两例的情况下，你的解决方案，包括节点的情况下，和你排除从解结。

• 使用动态编程：从树的叶子到树的根。

tree  binary-search-tree  graph-algorithm  depth-first-search  breadth-first-search