r*****t
发帖数: 68 | 1 Problem: given a binary tree, if parent is added to a set, then its chidren
cannot. Find the max number of nodes in such independent set.
我的想法：存在一个最大的set是包括所有的叶子。 所以选所有的叶子，然后从叶子层
开始逆推，若至少一个子点被选，则父点不选；若两个子点都没选（或唯一的子点没选
），则父点选。 这样构造一个set. 而且这是一个最大set。
存在一个最大的set是包括所有的叶子， 因为对任意的最大set，可以分为叶点和叶点
的父以前的点(1)，和叶点和叶点的父(2) 两部分。由于一点最多有2个子点，那么选所
有叶点，不选所有叶点的父不会减少(2). 所以保持1， 改2为只选叶点， 也是最大set.
逆推: 因为第一步选所有叶点，不选所有叶点的父。之后，在剩下的树里，叶点上推2
层的点就又相当于新树叶点。递归
如果树只有两层，选所有叶点定可构成最大的set
非cs菜鸟请大牛指点，这个想法对吗？ |
h*********o
发帖数: 230 | 2 加了父节点就加子节点的子节点，或者只要父节点，两种情况recursion吧
chidren
set.
2
【在 r*****t 的大作中提到】
: Problem: given a binary tree, if parent is added to a set, then its chidren
: cannot. Find the max number of nodes in such independent set.
: 我的想法：存在一个最大的set是包括所有的叶子。 所以选所有的叶子，然后从叶子层
: 开始逆推，若至少一个子点被选，则父点不选；若两个子点都没选（或唯一的子点没选
: ），则父点选。 这样构造一个set. 而且这是一个最大set。
: 存在一个最大的set是包括所有的叶子， 因为对任意的最大set，可以分为叶点和叶点
: 的父以前的点(1)，和叶点和叶点的父(2) 两部分。由于一点最多有2个子点，那么选所
: 有叶点，不选所有叶点的父不会减少(2). 所以保持1， 改2为只选叶点， 也是最大set.
: 逆推: 因为第一步选所有叶点，不选所有叶点的父。之后，在剩下的树里，叶点上推2
: 层的点就又相当于新树叶点。递归
|
o*****n
发帖数: 189 | 3 分层记录所有node, 单数一个，双数一个。然后比较单，双数里哪个node 多.
对吗？ |
o*****n
发帖数: 189 | |
c*******7
发帖数: 438 | 5 你的做法是对的。以所有叶子节点的集合作为第一层，做ＢＦＳ，每奇数层的所有节点
加入到结果的集合中，可以得到最大集合。
证明：
对任一在最大集合中的节点Ｎ，若其有子节点不在该集合中且该子节点为叶子节点，可
以将该节点换成其子节点，集合的ｃｏｕｎｔ不变或增加（因为已经是最大集合，所以
肯定不变）。
这一步可以证明必有一个最大集合包含所有的叶节点。
然后递归论证，从原来的树中将这个最大集合的所有叶节点（最外面一层）和他们的父
节点去掉，剩下的树继续求最大集合，同第一步可以继续找到一个最大集合包含所有这
个切割后的树的所有叶子节点。如此递归最后得到一个最大集合。 |
c******0
发帖数: 260 | |
r***o
发帖数: 82 | 7 貌似用greedy,
就是从叶子出发，每次set.add一个叶子，然后树上remove掉它的parent...然后递归到
树为空 |
