题解概述

该题目要求我们对原始二叉树中的节点进行消除，这些节点的值与参照二叉树中相同层级的节点值相同。消除的数量受到参照树中对应节点值出现次数的限制。最后，我们需要输出消除后原始二叉树中有效节点的值，按频率从高到低排列。

思路：哈希+模拟

记录原始二叉树以及参照二叉树的每一层中每个不同值出现的次数，可以通过层序遍历、哈希记录、按2的幂次步长扫描节点等方式实现。

根据两棵树的计数对每一层做差集，消除节点后，对剩余节点按照题目要求排序并输出即可。

解题思路

1. 数据输入与初始化：

   • 通过输入函数读取原始二叉树和参照二叉树的节点值，分别存入两个向量中。
   • 利用两个整型变量n和m来记录两个树的节点数，方便后续操作。

2. 计数节点频率：

   • 使用层序遍历的方式对两个二叉树进行处理，逐层统计每一层中不同值的出现次数。为此，我们可以利用哈希表（unordered_map）来记录每一层的节点值及其频率。

3. 消除节点：

   • 在统计完每一层的节点频率后，对应地进行消除操作。具体做法是遍历原始树的当前层节点，如果该节点的值在参照树的同一层中存在且未完全消除，则标记为已消除（使用一个布尔数组vis）。
   • 需要注意的是，消除的数量受限于参照树中相应节点的数量，因此我们在消除后需更新频率表。

4. 统计有效节点：

   • 遍历原始树的节点，统计未被消除的节点的值及其出现频率，存入另一个哈希表中。

5. 排序与输出：

   • 最后，将未消除节点的频率和节点值存入一个结果向量中。为了便于排序，使用频率的负值和节点值的负值（从而实现降序排序）。
   • 排序后，输出有效节点的值。如果没有有效节点，则输出0。

代码

java

import java.util.*;

public class Main {

    // 用于封装返回的数据
    static class Data {
        int n;
        int m;
        int[] a;
        int[] b;

        Data(int n, int[] a, int m, int[] b) {
            this.n = n;
            this.a = a;
            this.m = m;
            this.b = b;
        }
    }

    // 初始化函数，用于输入数据并进行初始化
    public static Data init() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 输入数组a的大小
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();  // 输入数组a的元素
        }

        int m = scanner.nextInt();  // 输入数组b的大小
        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            b[i] = scanner.nextInt();  // 输入数组b的元素
        }

        return new Data(n, a, m, b);  // 返回封装好的数据对象
    }

    // 求解函数，执行主要的匹配逻辑
    public static void solve(int n, int[] a, int m, int[] b) {
        boolean[] vis = new boolean[n];  // 初始化vis数组，默认全为false
        int i = 0;  // i代表当前的起始位置
        int j = 0;  // j控制步长（每次翻倍）

        while (i < n && i < m) {
            Map<Integer, Integer> mp = new HashMap<>();  // 使用HashMap记录b数组中元素的频次

            for (int k = 0; k < (1 << j); k++) {
                mp.put(b[i + k], mp.getOrDefault(b[i + k], 0) + 1);  // 统计b数组中当前子数组的元素频次
            }

            for (int k = 0; k < (1 << j); k++) {
                if (mp.getOrDefault(a[i + k], 0) > 0) {  // 如果a数组中的元素在b数组中存在且未完全匹配
                    vis[i + k] = true;  // 标记该元素为已匹配
                    mp.put(a[i + k], mp.get(a[i + k]) - 1);  // 对应频次减一
                }
            }

            i += (1 << j);
            j += 1;
        }

        Map<Integer, Integer> freq = new HashMap<>();  // 用于存储未匹配的a数组元素及其频次

        for (int k = 0; k < n; k++) {
            if (!vis[k]) {
                freq.put(a[k], freq.getOrDefault(a[k], 0) + 1);  // 统计未匹配的a数组元素
            }
        }

        List<int[]> ans = new ArrayList<>();  // 用于存储结果

        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            ans.add(new int[]{-entry.getValue(), -entry.getKey()});  // 将频次和元素存入结果，并取负以便排序
        }

        ans.sort((o1, o2) -> {
            if (o1[0] != o2[0]) {
                return Integer.compare(o1[0], o2[0]);
            } else {
                return Integer.compare(o1[1], o2[1]);
            }
        });  // 按频次和元素值排序

        for (int[] p : ans) {
            System.out.print(-p[1]);  // 输出排序后的元素
        }

        if (ans.isEmpty()) {
            System.out.print(0);  // 如果结果为空，输出0
        }
    }

    // 主函数
    public static void main(String[] args) {
        Data data = init();  // 初始化数据
        solve(data.n, data.a, data.m, data.b);  // 进行求解
    }
}

Python

from collections import defaultdict

# 初始化函数，用于输入数据并进行初始化
def init():
    n = int(input())  # 输入数组a的大小
    a = list(map(int, input().split()))  # 输入数组a的元素

    m = int(input())  # 输入数组b的大小
    b = list(map(int, input().split()))  # 输入数组b的元素

    return n, a, m, b

# 求解函数，执行主要的匹配逻辑
def solve(n, a, m, b):
    vis = [False] * n  # 初始化vis数组，默认全为False
    i = 0  # i代表当前的起始位置
    j = 0  # j控制步长（每次翻倍）

    while i < n and i < m:
        mp = defaultdict(int)  # 使用defaultdict记录b数组中元素的频次

        for k in range(1 << j):
            mp[b[i + k]] += 1  # 统计b数组中当前子数组的元素频次

        for k in range(1 << j):
            if mp[a[i + k]] > 0:  # 如果a数组中的元素在b数组中存在且未完全匹配
                vis[i + k] = True  # 标记该元素为已匹配
                mp[a[i + k]] -= 1  # 对应频次减一

        i += (1 << j)
        j += 1

    freq = defaultdict(int)  # 用于存储未匹配的a数组元素及其频次

    for i in range(n):
        if not vis[i]:
            freq[a[i]] += 1  # 统计未匹配的a数组元素

    ans = []  # 用于存储结果

    for key, value in freq.items():
        ans.append((-value, -key))  # 将频次和元素存入结果，并取负以便排序

    ans.sort()  # 按频次和元素值排序

    for _, key in ans:
        print(-key, end="")  # 输出排序后的元素

    if not ans:
        print(0)  # 如果结果为空，输出0

# 主函数
if __name__ == "__main__":
    n, a, m, b = init()  # 初始化数据
    solve(n, a, m, b)  # 进行求解

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

// 初始化函数，用于输入数据并进行初始化
void init(int &n, vector<int> &a, int &m, vector<int> &b) {
    cin >> n;  // 输入数组a的大小
    a.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];  // 输入数组a的元素
    }

    cin >> m;  // 输入数组b的大小
    b.resize(m);
    for (int i = 0; i < m; ++i) {
        cin >> b[i];  // 输入数组b的元素
    }
}

// 求解函数，执行主要的匹配逻辑
void solve(int n, const vector<int> &a, int m, const vector<int> &b) {
    vector<bool> vis(n, false);  // 初始化vis数组，默认全为false
    int i = 0;  // i代表当前的起始位置
    int j = 0;  // j控制步长（每次翻倍）

    while (i < n && i < m) {
        unordered_map<int, int> mp;  // 使用unordered_map记录b数组中元素的频次

        for (int k = 0; k < (1 << j); ++k) {
            mp[b[i + k]] += 1;  // 统计b数组中当前子数组的元素频次
        }

        for (int k = 0; k < (1 << j); ++k) {
            if (mp[a[i + k]] > 0) {  // 如果a数组中的元素在b数组中存在且未完全匹配
                vis[i + k] = true;  // 标记该元素为已匹配
                mp[a[i + k]] -= 1;  // 对应频次减一
            }
        }

        i += (1 << j);
        j += 1;
    }

    unordered_map<int, int> freq;  // 用于存储未匹配的a数组元素及其频次

    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            freq[a[i]] += 1;  // 统计未匹配的a数组元素
        }
    }

    vector<pair<int, int>> ans;  // 用于存储结果

    for (const auto &kv : freq) {
        ans.emplace_back(-kv.second, -kv.first);  // 将频次和元素存入结果，并取负以便排序
    }

    sort(ans.begin(), ans.end());  // 按频次和元素值排序

    for (const auto &p : ans) {
        cout << -p.second;  // 输出排序后的元素
    }

    if (ans.empty()) {
        cout << 0;  // 如果结果为空，输出0
    }
}

// 主函数
int main() {
    int n, m;
    vector<int> a, b;
    init(n, a, m, b);  // 初始化数据
    solve(n, a, m, b);  // 进行求解
    return 0;
}

题目内容

给定原始二叉树和参照二叉树(输入的二叉树均为满二叉树，二叉树节点的值范围为$[1,1000]$，

二叉树的深度不超过$1000$)，现对原始二叉树和参照二叉树中相同层级且值相同的节点进行消除，

消除规则为原始二叉树和参照二叉树中存在多个值相同的节点只能消除等数量的，

消除后的节点变为无效节点，

请按节点值出现频率从高到低输出消除后原始二叉树中有效节点的值(如果原始二叉树消除后没有有效节点返回$0$)。

输入描述

原始二叉树中的节点个数

原始二叉树

参照二叉树中的节点个数

参照二叉树

输出描述

原始二叉树中有效节点的值，按出现频率从高到低排序(相同频率的值按大小排序)，相同频率的值按降序排序

样例1

输入

7
1 3 3 3 4 5 6
3
2 3 4

输出

36541

解释

原始二叉树$A$消除参照二叉树$B$中的重复元素后，有效节点剩余$2$个$3$，$1$个$6$，$1$个$5$，$1$个$4$，$1$个$1$，$3$出现的频率$2$，$6$、$5$、$4$、$1$出现的频率为$1$，按值从大到小排序，所以排序结果为$36541$.

样例2

输入

15
5 6 6 6 7 7 7 8 8 9 9 7 7 5 6
7
5 6 6 7 7 8 8

输出

79865

解释

原始二叉树$A$消除参照二叉树$B$中的重复元素后，有效节点剩余$3$个$7$，$2$个$9$，$2$个$8$，$2$个$6$，$1$个$5$，$8$出现的频率为$3$，$7$出现的频率为$2$，$6$出现的频率为$2$，$6$的值比$5$大，所以排序结果为$79865$