题解概述

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

思路：哈希+模拟

记录原始二叉树以及参照二叉树的每一层中每个不同值出现的次数，可以通过层序遍历、哈希记录、按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;
}