Interjay 已指出您的答案为何不正确。该问题可以用递归算法解决find-max-independent
给定二叉树,考虑两种情况:
- 假设根节点是,最大独立集是多少
包括?
- 给定根节点,最大独立集是多少
不包括在内?
在情况 1 中,由于包含根节点,因此它的子节点都不能包含在内。因此我们将值相加find-max-independent
root 的孙子的值,加上 root 的值(必须包含在内),然后返回该值。
在情况 2 中,我们返回最大值find-max-independent
子节点的数量(如果有的话)(我们只能选择一个)
该算法可能看起来像这样(在 python 中):
def find_max_independent ( A ):
N=len(A)
def children ( i ):
for n in (2*i+1, 2*i+2):
if n<N: yield n
def gchildren ( i ):
for child in children(i):
for gchild in children(child):
yield gchild
memo=[None]*N
def rec ( root ):
"finds max independent set in subtree tree rooted at root. memoizes results"
assert(root<N)
if memo[root] != None:
return memo[root]
# option 'root not included': find the child with the max independent subset value
without_root = sum(rec(child) for child in children(root))
# option 'root included': possibly pick the root
# and the sum of the max value for the grandchildren
with_root = max(0, A[root]) + sum(rec(gchild) for gchild in gchildren(root))
val=max(with_root, without_root)
assert(val>=0)
memo[root]=val
return val
return rec(0) if N>0 else 0
一些测试用例说明:
tests=[
[[1,2,3,4,5,6], 16], #1
[[-100,2,3,4,5,6], 6], #2
[[1,200,3,4,5,6], 200], #3
[[1,2,3,-4,5,-6], 6], #4
[[], 0],
[[-1], 0],
]
for A, expected in tests:
actual=find_max_independent(A)
print("test: {}, expected: {}, actual: {} ({})".format(A, expected, actual, expected==actual))
示例输出:
test: [1, 2, 3, 4, 5, 6], expected: 16, actual: 16 (True)
test: [-100, 2, 3, 4, 5, 6], expected: 15, actual: 15 (True)
test: [1, 200, 3, 4, 5, 6], expected: 206, actual: 206 (True)
test: [1, 2, 3, -4, 5, -6], expected: 8, actual: 8 (True)
test: [], expected: 0, actual: 0 (True)
test: [-1], expected: 0, actual: 0 (True)
测试用例1
![test case 1](https://i.stack.imgur.com/nQUzi.png)
测试用例2
![test case 2](https://i.stack.imgur.com/pcTkI.png)
测试用例3
![test case 3](https://i.stack.imgur.com/TQ2YW.png)
测试用例4
![test case 4](https://i.stack.imgur.com/xTs4n.png)
记忆算法的复杂度为O(n)
, since rec(n)
每个节点调用一次。这是使用深度优先搜索的自上而下的动态规划解决方案。
(测试用例插图由 leetcode 的交互式二叉树编辑器提供)