二叉树染色

该题解采用递归方法进行动态规划。首先定义一个辅助函数 maxSubTree，该函数返回一个列表，其中包含以当前节点为根的子树内，各个可能的蓝色节点群组的最大值累计。列表中的每个位置i表示恰好有i个连续节点被染色的情况下，可以获得的最大价值。函数首先处理基本情况，如果当前节点为空，则返回一个只包含0的列表。然后，它递归地计算左右子树的最大价值列表。使用两层循环遍历左右子树返回的列表，来确定在当前节点下，形成不同大小的蓝色节点群组的最大价值。外层循环和内层循环分别遍历左子树和右子树返回的列表，通过将左右子树的某些价值组合并加上当前节点的价值，来更新结果列表。最后，返回整棵树调用 maxSubTree 后的最大价值。

时间复杂度: O(n*k^2)

空间复杂度: O(n*k)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxValue(self, root: TreeNode, k: int) -> int:

        def maxSubTree(node):
            # 如果节点为空，返回包含一个0的列表
            if not node:
                return [0]

            # 递归计算左右子树的最大价值列表
            l = maxSubTree(node.left)
            r = maxSubTree(node.right)

            # 初始化当前节点的最大价值列表
            res = [0] * (k + 1)
            res[0] = l[-1] + r[-1]
            # 更新当前节点下各种可能的连续蓝色节点群组的最大价值
            for i in range(len(l)):
                for j in range(min(len(r), k - i)):
                    res[i + j + 1] = max(res[i + j], res[i + j + 1], l[i] + r[j] + node.val)
            return res[: len(l) + len(r)]
        
        # 返回整棵树的最大价值
        return max(maxSubTree(root))