设彩灯颜色在集合 {1,2,3,4,5} 上循环。按某个节点一次,会使该节点及其整棵子树的颜色都加 1(模 5)。
把颜色映射为 0…4 更便于计算:令 c0 = c - 1,则每次点击相当于对子树的颜色 “+1(mod 5)”。
若从根到当前节点一共累计了 inc 次加 1(mod 5),则当前节点颜色为 (initial0 + inc) % 5。要让它变成 target0,最少还需在当前节点再按
d = (target0 - initial0 - inc) mod 5 (取 0..4 之间)
圣诞节快到了,有一棵挂满彩灯的二叉树,需要你来按照图纸装饰。彩灯有 5 种颜色变化,分别用 1−5 表示。
1 表示红色,2 表示黄色,3 表示蓝色,4 表示紫色,5 表示绿色。
每个节点都一个颜色控制器,每按一下,就会将当前彩灯以及以当前节点为根节点的子树上的所有节点,切换到下一个颜色(红->黄 ->蓝->紫>绿->红...)循环切换。
给定二叉树的初始状态 initial 和 目标状态 target ,两者都以层序遍历产出的一维数组表示。数组元素对应对应位置节点的颜色,0 表示该节点没有彩灯。