二叉树染色

/*
 * Problem: Given a binary tree with a root node, where each node has a value and is initially white. You can color nodes with blue dye.
 * You need to ensure that the maximum number of blue connected nodes does not exceed k. Find the maximum sum of the values of the blue nodes.
 * 
 * Approach using Java Streams:
 * 1. Define a TreeNode class to represent nodes in the binary tree.
 * 2. Implement a recursive function using streams to traverse and process the tree.
 */

import java.util.Arrays;
import java.util.stream.IntStream;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int maxBlueNodesValue(TreeNode root, int k) {
        return dfs(root, k)[0];
    }

    private int[] dfs(TreeNode node, int k) {
        if (node == null) return new int[k + 1];

        int[] left = dfs(node.left, k);
        int[] right = dfs(node.right, k);

        int[] dp = new int[k + 1];

        // If we don't color the current node
        IntStream.range(0, k + 1).forEach(i -> dp[0] = Math.max(dp[0], left[i] + right[i]));

        // If we color the current node
        IntStream.range(1, k + 1).forEach(i -> {
            IntStream.range(0, i).forEach(j -> dp[i] = Math.max(dp[i], node.val + left[j] + right[i - 1 - j]));
        });

        return dp;
    }
}