现在有一颗二叉树,初始化的结点都是白色的,现在需要把若干个结点涂成黑色,使得不会出现父结点和它的两个非空孩子结点都是白色

用二进制表示二叉树的状态

1表示进行先序深度遍历,0表示叶子结点

例如

1100100的二叉树形态是

    #
   / \
  o   o

只要对根结点#进行着色一次操作就可以了

例如

1110010011000

对应的二叉树形态是

      o
    /  \
   #    o
  / \  /  \
 o   o o   NULL

这个只要对#结点进行着色就可以了

输入:一个长度小于等于100的二进制数

输出:最少操作次数


还有版本2的

每次对结点进行着色操作都会改变操作结点以及它的非空孩子结点的颜色,如果该结点原色是白色则会变成黑色,如果该结点原色是黑色,则会重新变回白色,并且初始化已经有若干个结点是黑色的,问最少多少次操作才能把所有结点变成黑色?

用w表示白色,b表示黑色,#表示叶子结点(已知结点小于等于100个)

输出最少操作次数

例如:

输入:ww##bb##w##
输出:3

这个问题看上去不是很难,但感觉比较好玩~我虽然找到方法,但不太会证明该方法的正确性,发出来看看怎么理解?~

[此贴子已经被作者于2018-6-9 16:03编辑过]

你这个是第一问么,看上去好像是第二问的样子~第一问的创建就只有0和1两种情况而已,怎么会有三种情况?具体没有怎么看,或者到时要看看结果才能说些什么(想不到原本思路简单的东西用代码表示会这么复杂,不知道是本来就那么复杂还是只是没有找到简单的表述方式而已)

个人感觉第二个版本其实比较好弄一些,要是代码复杂说说思路也是可以的~

[此贴子已经被作者于2018-6-10 15:43编辑过]

算了,先结贴~

知道第二问一种状态只有唯一一个对应解,我,知道方法就不弄代码了,其实稍微比划一下就知道怎么弄了,不用多说~