My approach is dfs with memoization. First, generate a tree from given input, then run the recursive function (with cache) on the tree. Let's define the function f(isGreen,node) as the {minimum|maximum} number of green color nodes in the subtree below @node and @node itself, when the @node have color {green if @isGreen=True, red or blue otherwise}.
Now, we will consider the case we want the maximum number of green nodes.
If the number of children for @node is 0, f(isGreen,node) is defined as follows:
if @isGreen==True:
f(isGreen,node) = 1
else:
f(isGreen,node) = 0
If the number of children for @node is 1, f(isGreen,node) is defined as follows:
if @isGreen==True:
f(isGreen,node) = f(False,@node's child) + 1
else:
f(isGreen,node) = max(f(True,@node's child),f(False,@node's child))
If the number of children for @node is 2, f(isGreen,node) is defined as follows:
if @isGreen==True:
f(isGreen,node) = f(False,@node's 1st child) + f(False,@node's 2nd child) + 1
else:
A = f(True,@node's 1st child) + f(False,@node's 2nd child)
B = f(False,@node's 1st child) + f(True,@node's 2nd child)
f(isGreen,node) = max(A,B)
For the case we want the minimum number of green nodes, just change max() to min().
