leetcode LCP 34. 二叉树染色 golang-木庄网络博客

本文摘自网络，作者，侵删。

LCP 34. 二叉树染色

这道题理解错题意了改了n久自己好菜

题目

小扣有一个根结点为 root 的二叉树模型，初始所有结点均为白色，可以用蓝色染料给模型结点染色，模型的每个结点有一个 val 价值。小扣出于美观考虑，希望最后二叉树上每个蓝色相连部分的结点个数不能超过 k 个，求所有染成蓝色的结点价值总和最大是多少？

解题思路

设 dp[k] 表示在当前节点染色了k的最大值。
则 dp[0] = max(left,right),dp[k]=max(dp_left[n],dp_right[k-n-1]) + root.val

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func maxValue(root *TreeNode, k int) int {
    A := dfs(root, k)
    ans := 0
    for _, item := range A {
        if ans < item {
            ans = item
        }
    }
    return ans
}

func dfs(root *TreeNode, k int) []int {
    A := make([]int, k+1)
    if root == nil {
        return A
    }
    left := dfs(root.Left, k)
    right := dfs(root.Right, k)
    t := 0
    for _, item := range left {
        if t < item {
            t = item
        }
    }
    A[0] += t
    t = 0
    for _, item := range right {
        if t < item {
            t = item
        }
    }
    A[0] += t
    A[1] = left[0] + right[0] + root.Val
    for n := 2; n <= k; n++ {
        for i := 0; i < n; i++ {
            j := n - i - 1

            if A[n] < left[i]+right[j]+root.Val {
                A[n] = left[i] + right[j] + root.Val
            }
        }
    }
    // A[1] = left[0] + right[0] + root.Val
    // for i := 1; i <= k; i++ {
    //  A[i] = left[i-1] + right[i-1]
    //  if left[i-1]!=0 && A[i] < left[i-1]+right[0] {
    //      A[i] = left[i-1] + right[0]
    //  }
    //  if right[i-1] != 0 && A[i] < right[i-1]+left[0] {
    //      A[i] = right[i-1] + left[0]
    //  }
    // if i == 1 || A[i]!=0{
    //      A[i] += root.Val
    // }
    // }
    return A
}

本文来自：简书

感谢作者：lucasgao

查看原文：leetcode LCP 34. 二叉树染色 golang