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 你的做法是对的。以所有叶子节点的集合作为第一层,做BFS,每奇数层的所有节点
加入到结果的集合中,可以得到最大集合。
证明:
对任一在最大集合中的节点N,若其有子节点不在该集合中且该子节点为叶子节点,可
以将该节点换成其子节点,集合的count不变或增加(因为已经是最大集合,所以
肯定不变)。
这一步可以证明必有一个最大集合包含所有的叶节点。
然后递归论证,从原来的树中将这个最大集合的所有叶节点(最外面一层)和他们的父
节点去掉,剩下的树继续求最大集合,同第一步可以继续找到一个最大集合包含所有这
个切割后的树的所有叶子节点。如此递归最后得到一个最大集合。 |
c******0 发帖数: 260 | |
r***o 发帖数: 82 | 7 貌似用greedy,
就是从叶子出发,每次set.add一个叶子,然后树上remove掉它的parent...然后递归到
树为空 |