动态规划之在二叉树中使用DP

二叉树染色-题目描述

小扣有一个根结点为 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

详细思路

个人走的弯路（可略）

这道题也想了一段时间才做出来，最开始感觉是动态规划的思路，但是第一次在树结构中使用动态规划确实没有什么经验，想着会不会要先把树结构改变一下，例如做成邻接表

然后觉得这种做法也很麻烦，又想到会不会是是贪心算法呢，先选取树中最大的元素，依次考虑。发现如果这样做的话有需要进行并查集等操作，更重要的是这种思路是不是一定正确的，后来举例子反证了思路的错误

k为2

5，9，null,8，null,null,null,5

如果先选取最大的，是考虑9，8，但是明显5，9，5的组合更好

正确思路

最后花了几遍二叉树，经过思考，如果从底部往上开始，那么一个节点只需要考虑左右两个节点，那么也仅仅有如下几种情况
假如目前k=4

1. 仅连接左节点，那么左节点有0，1，2三种情况，值分别为sum1，sum2，sum3那么父节点就对应有1，2，3，值分别为sum1+node.val，sum2+node.val，sum3+node.val
2. 仅连接右节点，情况和上述一致，考虑的是子节点有0，1，2，3，4情况的话，父节点也不能连接超过
3. 连接左右两个节点，那么就是对左节点和右节点情况的组合了，两个for循环遍历
4. 两个子节点都不连接，那么此时的值为左右节点最大值之和！

我们在改节点设置一个长度为k+1的array数组，分别记录该节点已经连接了多少个
array1代表左节点数组，array2代表右节点数组

1. 仅连接左节点 array[i+1]=array1[i]+array2[0]+node.val
2. 仅连接右节点 array[i+1]=array2[i]+array1[0]+node.val
3. 连接左右节点 array[i+j+1]=array1[i]+array2[j]+node.val
4. 左右节点都不连接 array[0]=array1数组中最大值+ array2+数组中最大值

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int k;
    public int maxValue(TreeNode root, int k) {
        this.k=k;
        int[] array=Bfs(root);
        int max=0;
        for (int i = 0; i < array.length; i++) {
            max=Math.max(array[i],max);
        }
        return max;
    }


    public int[] Bfs(TreeNode node){
        if(node==null)return null;
        //获得左节点数组情况，其中数组下标代表该节点已经连接了i个节点，下标对应的值代表连接i个节点情况下最大价值和
        int[] array1=Bfs(node.left);
        //同上
        int[] array2=Bfs(node.right);
        /*
        1.仅连接左节点 array[i+1]=array1[i]+array2[0]+node.val
        2。仅连接右节点 array[i+1]=array2[i]+array1[0]+node.val
        3。连接左右节点 array[i+j+1]=array1[i]+array2[j]+node.val
        （第三种情况其实包含了1，2情况，因为i或j取0时候就是1，2情况）
        4。左右节点都不连接 array[0]=左右最大的值
         */
        int[] array=new int[k+1];
        int max=0;
        //如果左右节点都为空，那么array只有0和1两种情况，数组默认array[0]为0了
        if(array1==null&&array2==null){
            array[1]=node.val;
        }else if(array1==null){
            for (int i = 0; i < array2.length; i++) {
                max=Math.max(array2[i],max);
               if(i+1<array.length) array[i+1]=array2[i]+node.val;
            }
            array[0]=max;
        }else if(array2==null){
            for (int i = 0; i < array1.length; i++) {
                max=Math.max(array1[i],max);
                if(i+1<array.length) array[i+1]=array1[i]+node.val;
            }
            array[0]=max;
        }else {
            for (int i = 0; i < array1.length; i++) {
                for (int j = 0; j < array2.length; j++) {
                    max=Math.max(max,array1[i]+array2[j]);
                    if(i+j+1<array.length)array[i+j+1]=Math.max(array[i+j+1],array1[i]+array2[j]+node.val);
                }
            }
            array[0]=max;
        }
        return array;
    }

}

传送门

LCP 34. 二叉树染色

https://leetcode-cn.com/problems/er-cha-shu-ran-se-UGC/