题面描述

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

思路: DFS

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

题解

在无线通信设备中，超外差接收机的信号处理可以通过构建满二叉树来实现。这个树的每个节点存储当前子树的最大值和最小值，以便在后续的信号处理中快速计算频率的范围。具体步骤如下：

1. 树的构建：我们从下往上建立满二叉树，叶子节点直接使用给定的目标频率值。非叶子节点通过其左右孩子节点更新自身的最大值和最小值。具体而言，叶子节点的最大值和最小值相同，父节点的最大值为其两个孩子的最大值，最小值为其两个孩子的最小值。

2. DFS遍历：构建完树后，使用深度优先搜索（DFS）从上到下遍历树。每次遍历时，携带一个参数表示所有父节点的值的和，这样可以在计算当前节点的最终值时，减去父节点的和。

3. 输出结果：最终，输出每个节点的值，表示它在树中的状态。

代码

C++

#include <bits/stdc++.h>

using namespace std;

using ll = long long; // 定义长整型别名
using pii = pair<int, int>; // 定义一个整数对，用于存储最大值和最小值

int main() {
    ios::sync_with_stdio(0); // 加速输入输出
    cin.tie(0);
    
    int n;
    cin >> n; // 读取叶子节点的数量
    vector<int> a(n + 1); // 用于存储叶子节点的目标频率值
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; // 读取每个叶子节点的目标频率值
    }
    
    vector<ll> seg(n * 2); // 用于存储树节点的值，大小为2n
    
    // 建树函数，返回当前节点的最小值和最大值
    function<pii(int, int, int)> build = [&](int x, int l, int r) -> pii { 
        if (l == r) { // 如果到达叶子节点
            seg[x] = a[l]; // 叶子节点的值为目标频率值
            return {a[l], a[l]}; // 返回最小值和最大值（相同）
        } else {
            int mid = l + (r - l) / 2; // 计算中间位置
            pii a = build(x * 2, l, mid); // 递归建造左子树
            pii b = build(x * 2 + 1, mid + 1, r); // 递归建造右子树
            int mi = min(a.first, b.first); // 当前节点的最小值
            int mx = max(a.second, b.second); // 当前节点的最大值
            seg[x] = (mx + mi) / 2; // 当前节点的值为最大值和最小值的平均值
            return {mi, mx}; // 返回当前节点的最小值和最大值
        }
    };

    build(1, 1, n); // 从根节点开始建树

    // DFS遍历函数，x为当前节点，p为父节点值的和
    function<void(int, ll)> dfs = [&](int x, ll p) -> void { 
        if (x >= n * 2) return; // 超出节点范围，结束递归
        seg[x] -= p; // 当前节点值减去父节点的和
        // 递归遍历左右子树，将当前节点值和传递给孩子节点
        dfs(x * 2, p + seg[x]); 
        dfs(x * 2 + 1, p + seg[x]);
    };

    dfs(1, 0); // 从根节点开始DFS，初始父节点值为0

    // 输出结果
    for (int i = 1; i < n * 2; i++) {
        cout << seg[i] << ' '; // 输出每个节点的值
    }
    cout << endl; // 换行
}

java

import java.util.Scanner;

public class Main {
    static int n;
    static int[] a;
    static long[] seg;

    static class Pair {
        int first, second;

        Pair(int f, int s) {
            first = f;
            second = s;
        }
    }

    static Pair build(int x, int l, int r) {
        if (l == r) { // 叶子节点的最大值和最小值一样
            seg[x] = a[l];
            return new Pair(a[l], a[l]);
        } else {
            int mid = l + (r - l) / 2;
            Pair a = build(x * 2, l, mid); // 左孩子建树
            Pair b = build(x * 2 + 1, mid + 1, r); // 右孩子建树
            int mi = Math.min(a.first, b.first); // 更新当前节点的孩子最大值
            int mx = Math.max(a.second, b.second); // 更新当前节点的孩子最小值
            seg[x] = (mx + mi) / 2; // 当前节点权值
            return new Pair(mi, mx);
        }
    }

    static void dfs(int x, long p) { // 从上向下遍历，将父节点的和作为参数向下传递
        if (x >= n * 2) return;
        seg[x] -= p;
        dfs(x * 2, p + seg[x]);
        dfs(x * 2 + 1, p + seg[x]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        a = new int[n + 1];
        seg = new long[n * 2 + 1];

        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }

        build(1, 1, n);
        dfs(1, 0);

        for (int i = 1; i < n * 2; i++) {
            System.out.print(seg[i] + " ");
        }
        System.out.println();
    }
}

python

import sys

n = int(input())
a = [0] + list(map(int, input().split()))

seg = [0] * (n * 2)

def build(x, l, r):
    if l == r: # 叶子节点的最大值和最小值一样
        seg[x] = a[l]
        return (a[l], a[l])
    else:
        mid = l + (r - l) // 2
        a_l, a_r = build(x * 2, l, mid) # 左孩子建树
        b_l, b_r = build(x * 2 + 1, mid + 1, r) # 右孩子建树
        mi = min(a_l, b_l) # 更新当前节点的孩子最大值
        mx = max(a_r, b_r) # 更新当前节点的孩子最小值
        seg[x] = (mx + mi) // 2 # 当前节点权值
        return (mi, mx)

build(1, 1, n)

def dfs(x, p): # 从上向下遍历，将父节点的和作为参数向下传递
    if x >= n * 2:
        return
    seg[x] -= p
    dfs(x * 2, p + seg[x])
    dfs(x * 2 + 1, p + seg[x])

dfs(1, 0)

for i in range(1, n * 2):
    print(seg[i], end=' ')

print()