题目描述

由字符串 GASTON 构建的二叉搜索树如图所示。

该数据结构有多种实现方式。一种直观但较占空间的方法是使用 一维数组 来表示树结构。

在这种方法中：

• 根节点存储在位置 0。
• 对于任意位置 i 的节点：
  • 它的左子节点存储在位置 2i+1。
  • 它的右子节点存储在位置 2i+2。

例如，对于字符串 GASTON，构建的二叉搜索树在数组中的表示如下：

索引: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 …
内容: G A S     O   T         N

尽管这种表示方法会造成大量未被占用的数组单元，但它的实现不需要复杂的编程知识。

构建该树后，程序需要计算 数组中每个字母之间的空位数量，并输出这些数字。

输出输入格式

• 一个由 大写字母 组成的字符串。
• 字符串长度不超过 20 个字符。

输出格式

• 一串数字，表示构建出的二叉搜索树在数组中各字母间的空位数量。
• 每个数字之间用 一个空格 分隔。

示例

GASTON

0 0 2 0 4

解析：

• G 被放置在位置 0。
• A 是 G 的左子节点，放在 2*0+1 = 1。
• S 是 G 的右子节点，放在 2*0+2 = 2。
• T 是 S 的右子节点，放在 2*2+2 = 6。
• O 是 S 的左子节点，放在 2*2+1 = 5。
• N 是 O 的左子节点，放在 2*5+1 = 11。

这些节点在数组中的索引为：0 1 2 5 6 11。

这些索引之间的空位数依次为：

1-0-1 = 0

2-1-1 = 0

5-2-1 = 2

6-5-1 = 0

11-6-1 = 4