題目

小扣有一個根結點為 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題目，二叉樹題目