小 Z 是一个聪明的小学生,他用塑料管和橡皮泥搭成了一棵树,每个橡皮泥上都连接着一个向下的塑料管,有的连接着两根向上的塑料管,有的则连接着一些彩球。
然而,这个工艺品很快因为不平衡倒了下来。于是,小 Z 请教了和他在同一个班上的妹子小 C。在百科全书上看到天平平衡原理的小 C 知道,如果任何一块橡皮泥向上连接的两根管子的载重量之差超过一个彩球的重量,工艺品就会不平衡倒下来。由于彩球比较重,橡皮泥和塑料管的重量可以忽略不计。
由于移动彩球需要花时间拆卸和固定,小 C 希望移动最少次数彩球让这个工艺品平衡起来。你能帮助她吗?
给定一棵叶子带权值二叉树,保证每个非叶子结点都有两个儿子,权值只能是 或 。
你可以进行以下操作若干次:选中两个叶子,交换它们的权值。
定义一颗子树的权值为子树内所有叶子的权值之和。
你希望通过以上操作使得任意非叶子结点的左子树权值和右子树权值相差不超过 。
求达成以上目标需要的最少操作次数。