小算法题--5 三色二叉树
例如，下图所表示的二叉树可以用二叉树序列S=21200110来表示。
你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。
?
输入数据由多组数据组成。
每组数据仅有一行，不超过10000个字符，表示一个二叉树序列。
?
对于每组输入数据，输出仅一行包含两个整数，依次表示最多和最少有多少个点能够被染成绿色。
?
基本想法：对于root节点的每种染色方法，分别处理左右子树。
?????????????? 对于左右子树，问题变为规模更小的同类问题。
?????????????? 递归即得
?
class Node: def __init__(self,color=0,left=None,right=None): self.color=color self.left=left self.right=rightclass Tree: def __init__(self,root=None): self.root=roota=[1,1,2,2,0,0,2,0,1,0]t=Tree()t.root=Node()stack=[t.root]while len(a): n=a.pop(0) if n==2: p=stack.pop() p.left=Node() p.right=Node() stack.append(p.right) stack.append(p.left) elif n==1: p=stack.pop() p.left=Node() stack.append(p.left) else: stack.pop()def ColorTree_Max(root_c,root): if root is None: return 0 Max=0 root.color=root_c if root_c==1: Max+=1 Max+=max(ColorTree_Max(2,root.left)+ColorTree_Max(3,root.right), ColorTree_Max(3,root.left)+ColorTree_Max(2,root.right)) return Max elif root_c==2: Max+=max(ColorTree_Max(1,root.left)+ColorTree_Max(3,root.right), ColorTree_Max(3,root.left)+ColorTree_Max(1,root.right)) return Max else: Max+=max(ColorTree_Max(1,root.left)+ColorTree_Max(2,root.right), ColorTree_Max(2,root.left)+ColorTree_Max(1,root.right)) return Maxdef ColorTree_Min(root_c,root): if root is None: return 0 Min=0 root.color=root_c if root_c==1: Min+=1 Min+=min(ColorTree_Min(2,root.left)+ColorTree_Min(3,root.right), ColorTree_Min(3,root.left)+ColorTree_Min(2,root.right)) return Min elif root_c==2: Min+=min(ColorTree_Min(1,root.left)+ColorTree_Min(3,root.right), ColorTree_Min(3,root.left)+ColorTree_Min(1,root.right)) return Min else: Min+=min(ColorTree_Min(1,root.left)+ColorTree_Min(2,root.right), ColorTree_Min(2,root.left)+ColorTree_Min(1,root.right)) return Minprint max(ColorTree_Max(1,t.root),ColorTree_Max(2,t.root),ColorTree_Max(3,t.root))print min(ColorTree_Min(1,t.root),ColorTree_Min(2,t.root),ColorTree_Min(3,t.root))?
