题目

小扣有一个根结点为 root 的二叉树模型，初始所有结点均为白色，可以用蓝色染料给模型结点染色，

模型的每个结点有一个 val 价值。

小扣出于美观考虑，希望最后二叉树上每个蓝色相连部分的结点个数不能超过 k 个，

求所有染成蓝色的结点价值总和最大是多少？

示例 1：输入：root = [5,2,3,4], k = 2输出：12

解释：结点 5、3、4 染成蓝色，获得最大的价值 5+3+4=12

示例 2：输入：root = [4,1,3,9,null,null,2], k = 2 输出：16

解释：结点 4、3、9 染成蓝色，获得最大的价值 4+3+9=16

提示：1 <= k <= 10

1 <= val <= 10000

1 <= 结点数量 <= 10000

解题思路分析

1、动态规划+递归；时间复杂度O(n^3)，空间复杂度O(n^2)

func maxValue(root *TreeNode, k int) int {
   dp := dfs(root, k)
   return maxArr(dp)
}

func dfs(root *TreeNode, k int) []int {
   dp := make([]int, k+1) // dp[i]表示，染色数为i的最大值
   if root == nil {
      return dp
   }
   left := dfs(root.Left, k)
   right := dfs(root.Right, k)
   dp[0] = maxArr(left) + maxArr(right) // 当前节点不染色
   for i := 1; i <= k; i++ {            // 当前节点染色
      for j := 0; j < i; j++ {
         dp[i] = max(dp[i], left[j]+right[i-1-j]+root.Val)
      }
   }
   return dp
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

func maxArr(arr []int) int {
   res := 0
   for i := 0; i < len(arr); i++ {
      res = max(res, arr[i])
   }
   return res
}

总结

Medium题目，二叉树题目