题面描述

在无线通信设备中，超外差接收机通过将输入信号与本地产生的振荡波混频来变换频率。为了节省器件，设计了一种二又树型的混频器组，可以同时将信号搬移到不同的频率。给定一个完全二叉树的层数和每个叶子节点的目标频率值，我们需要计算树中每个节点的值，节点值由其所有叶子节点的最大值和最小值的平均值减去其所有父节点值的总和。最终以数组形式输出该二叉树的节点值。

思路: DFS

建立一个满二叉树，从下往上建树，每个节点存储当前最大值和最小值，叶子结点最大值和最小值一样，没个节点只需要考虑自己的左孩子和右孩子。由两个孩子来更新自身的最大值和最小值。从下往上建树后从上向下DFS，每层携带一个参数表示所有父亲的值的和。

题解

题目内容

在无线通信设备中通常使用超外差接收机，超外差接收机是利用本地产生的振荡波与输入信号混频，将输入信号频率变换为某个预先确定的频率的方法。也就是说，信号通过一个混频器后，频率就会搬移一个数值。在项目中由于要节省器件，混频器需要尽可能的共享，我们设计了二又树型的混频器组，可以同时把信号搬移到不同的频率上。

二又树为完全二叉树。我们给定二叉树的层数和从根节点开始到每个子节点的频率搬移总和输出二又树。

规则: 节点的值为它的所有叶子节点的目标频率值最大值和最小值的平均值 (非整数向下取整)减去 它所有父节点的总和。

满足:

• $A+B+D=10$
• $A+B+E=20$
• $A+C+F=30$
• $A+C+G=70$

输入描述

1. 叶子节点的数目 (必定是 $2^n$)，$1 \leq 叶子节点的数目 \leq 4096$
2. 每个叶子节点的目标频率值，二叉树的数组形式表示，把二叉树的结点依次自上而下，自左至右储存到数组中，$0 \leq 目标频率值 \leq 1000000$

输出描述

以数组形式的二叉树表示

样例

输入

4
18 24 2 3

输出

13 8 -11 -3 3 0 1

解释

第$0$层:所有叶子节点最大最小值的平均值为$(2+24)/2=13$所有父节点值为$0$，最终为 $13-0=13$

第$1$层左节点:所有叶子节点 最大最小值的平均值为$(18+24)/2=21$ 所有父节点值为13，最终为$21-13=8$

第$1$层右节点:所有叶子节点 最大最小值的平均值为$(2+3)/2=2$所有父节点值为$13$，最终为$2-13=-11$

第$2$层第$1$个节点:所有叶子节点 最大最小值的平均值为$18/1=18$所有父节点值为$13+8 =21$，最终为$18-21=-3$

第$2$层第$2$个节点: 所有叶子节点 最大最小值的平均值为$24/1=24$ 所有父节点值为$13+8 =21$，最终为$24 - 21=3$

第$2$层第$3$个节点: 所有叶子节点 最大最小值的平均值为$2/1=2$ 所有父节点值为$13+(-11)$=$2$，最终为$2-2 =0$

第$2$层第$4$个节点: 所有叶子节点 最大最小值的平均值为$3/1=3$ 所有父节点值为$13+(-11)=2$，最终为$3-2 = 1$