Coloring an AVL tree into a red-black tree with maximum black nodes

Question

What is an algorithm to color an AVL tree into a red-black tree using a maximal number of black nodes (or minimal number of red nodes)?

I was given this problem for a homework problem (color the nodes of an AVL tree to produce a valid red-black tree), and it gave me a thought: when I tried to write an algorithm for this, I tried to write an algorithm which colored as many of the nodes as possible black (e.g. given a perfect binary search tree, all nodes would be black), while the easiest solution (and the one given in the linked question) seems to give red-black trees with either minimal or near-minimal black depth (e.g. given a perfect binary search tree, layers would alternate between red and black). Coloring the most nodes black seemed to be a much harder problem, and while I have a partial solution written in a Java-like language, it is not correct.

// Helper to recursively color both children of a node; calls to
// colorAVLChildren do not on their own contribute to recursion
// depth, only the calls which they themselves make to colorAVL.
void colorAVLChildren(Node root) {
    if (root != nil) {
        colorAVL(root.left);
        colorAVL(root.right);
    }
}

void colorAVL(Node root) {
    if (root == nil) {
        return;
    }

    root.color = BLACK;

    // All nil nodes are already black, so regardless of the results
    // of the conditionals, the same effect will overall be had on the
    // coloring of the tree.
    if (root.left != nil) {
        root.left.color = BLACK;
    }
    if (root.right != nil) {
        root.right.color = BLACK;
    }

    if (root.isBalanced()) {
        colorAVLChildren(root.left);
        colorAVLChildren(root.right);
    } else {
        if (root.tallestChild().tallestChild() == nil) {
            root.tallestChild().color = RED;

            return;
        }

        // At least the taller of the tallest child's two children is
        // too tall for the next level of the recursion (i.e., would
        // be taller than other trees at that level, thus violating
        // its invariants); however, it is of the correct black-depth.
        // Therefore, it must be red so that its children are at the
        // correct black-depth, but must not be passed as an argument
        // to colorAVL.
        root.tallestChild().tallestChild().color = RED;

        // This part is incorrect if root.tallestChild().tallestChild() is not balanced
        colorAVLChildren(root.tallestChild().tallestChild());

        // If this tallest child is balanced, treat both of its
        // children the same; otherwise, don't color the shorter of
        // its children at this level of recursion, instead leaving it
        // to the next level to preserve the one-to-one correspondence
        // between tree height and recursion level.
        if (root.tallestChild().isBalanced()) {
            root.tallestChild().shortestChild().color = RED;
            // This part is incorrect if root.tallestChild().shortestChild() is not balanced
            colorAVLChildren(root.tallestChild().shortestChild());
        } else {
            colorAVL(root.tallestChild().shortestChild());
        }

        // The next level in this recursion is the level of the
        // shorter of the two children (as this is the only level
        // which both children are guaranteed to possess); therefore,
        // this shorter child must be colored at the next level of
        // recursion.
        colorAVL(root.shortestChild());
    }
}