登录
  • #刷题

三色‌‌‍‍‌‍‍‌‍‌‍‍‌‍‍‍‍‍‍‌‌‌‍‌‍‍‌‌‌‌‍‌二叉树,DP hard题,求讨论,求Python code

wwx_27
491
2
最近看面经搜集到的,力扣好像没有收录,如果有,是我太菜。。网上其实有C++的解法,但是自己写成Python不太确定,希望跟各位大佬一起讨论下。

题目如下

一棵二叉树可以按照如下规则表示成一个由 0、1、2 组成的字符序列,我们称之为 “二叉树序列 S”:

s = 0 表示该树没有子节点

s = 1 表示该树有一个子节点,S1为其子树的二叉树序列

s = 2 表示该树有两个子节点,S1和S2分别表示其两个子树的二叉树序列



你的任务是要对一棵二叉树的节点进行染色。

每个节点可以被染成红色、绿色或蓝色。

并且,一个节点与其子节点的颜色必须不同,如果该节点有两个子节点,那么这两个子节点的颜色也必须不相同。

给定一棵二叉树的二叉树序列,请求出这棵树中最多和最少有多少个点能够被染成绿色。

输入格式

仅有一行,表示一个二叉树序列。

输出格式

只有一行,包含两个数,依次表示最多和最少有多少个点能够被染成绿色。

数据范围

输入序列长度不超过 5×105。

输入样例:

1122002010

输出样例:

5 2
2条回复
热度排序

发表回复