求二叉树中最大独立集的大小--为什么有缺陷的“解”不起作用？

Question

1. 同一级别上的所有节点相互独立。
2. 交替级别上的所有节点彼此独立（没有父/子关系）

警告：我在考试时想出了这个，它并不漂亮，但我只是想看看我是否能至少争取到部分学分。

那么，为什么不能直接建立两个独立的集合（一个用于奇数级别，一个用于偶数级别）呢？

我的教授声称这行不通，但我不明白为什么。为什么行不通？

Answer 1

Interjay已经注意到为什么你的答案是不正确的。这个问题可以用递归算法find-max-internative来解决，在给定二叉树的情况下，该算法考虑两种情况：

1. 如果包含根节点，什么是最大独立集？
2. 如果不包括根节点，什么是最大独立集？

在情况1中，由于包含根节点，它的两个子节点都不能包含。因此，我们将root的孙函数的find-max-internative的值加上root的值（必须包含），并返回该值。

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)

测试用例4

memoized算法的复杂性是O(n)，因为每个节点调用一次rec(n)。这是一个使用深度优先搜索的自上而下的动态规划解决方案。

（测试用例插图由LeetCode的交互式二叉树编辑器提供）