二叉树消消乐 (100分) - 华为机试真题题解

题目描述

给定原始二叉树和参照二叉树(输入的二叉树均为满二叉树，二叉树节点的值范围为[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

C++

[代码仅供学习参考并未进行大量数据测试]

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n1, n2;
    // 统计每层节点出现的次数
    vector<unordered_map<int, int>> freq1;  // 原始二叉树的每层节点频率
    vector<unordered_map<int, int>> freq2;  // 参照二叉树的每层节点频率

    cin >> n1;  // 输入原始二叉树的节点个数
    // 统计原始二叉树的节点
    for (int i = 1, t, level = 0; i <= n1; i++) {
        cin >> t;  // 输入节点值
        if (i == (1 << level)) freq1.resize(++level);  // 判断当前层次
        freq1.back()[t]++;  // 统计该节点值在当前层级的出现次数
    }

    cin >> n2;  // 输入参照二叉树的节点个数
    // 统计参照二叉树的节点
    for (int i = 1, t, level = 0; i <= n2; i++) {
        cin >> t;  // 输入节点值
        if (i == (1 << level)) freq2.resize(++level);  // 判断当前层次
        freq2.back()[t]++;  // 统计该节点值在当前层级的出现次数
    }

    // 进行消除操作
    for (int level = 0; level < min(freq1.size(), freq2.size()); level++) {
        for (auto &p: freq2[level]) {  // 遍历参照二叉树中当前层的节点
            int k = p.first, cnt = p.second;  // 获取节点值和数量
            // 抵消掉原始二叉树中等数量的节点
            freq1[level][k] = max(0, freq1[level][k] - cnt);
        }
    }

    // 统计消除后的有效节点的出现次数
    unordered_map<int, int> freq;
    for (auto &mp: freq1) {
        for (auto &p: mp) {
            freq[p.first] += p.second;  // 将每层的剩余节点加入总频率统计
        }
    }

    // 将剩余节点转换为 vector 以便排序
    vector<pair<int, int>> tmp;
    for (auto &p: freq) {
        if (p.second > 0) tmp.emplace_back(p);  // 只保留有效节点（数量大于0）
    }

    // 如果没有有效节点，输出0
    if (tmp.empty()) {
        cout << 0 << endl;
        return 0;
    }

    // 对剩余节点按照频率降序排序，频率相同按值降序
    sort(tmp.begin(), tmp.end(), [](auto &p1, auto &p2) {
        if (p1.second != p2.second) {
            return p1.second > p2.second;  // 先按频率降序
        } else {
            return p1.first > p2.first;  // 再按值降序
        }
    });

    // 输出排序后的结果
    for (auto &p: tmp) {
        cout << p.first;  // 输出节点值
    }

    return 0;
}

题目分析

这道题属于树结构和频率统计类的问题。它结合了二叉树的层级遍历和频率统计，要求我们在消除重复元素后，按节点值的出现频率从高到低排序并输出。题目考察了数据结构的使用（特别是 unordered_map）以及对树的处理。

解题思路

1. 理解题意：
   • 我们有两棵二叉树：原始二叉树和参照二叉树。
   • 参照二叉树中的节点值需要在原始二叉树中进行消除。
   • 规则是，原始树和参照树中相同层次且值相同的节点可以消除，但只能消除等量的节点。
   • 消除后需要按照原始树中剩余节点的值出现频率（从高到低）排序，如果频率相同，则按值从大到小排序输出。
2. 步骤概述：
   • 先分别统计原始二叉树和参照二叉树每一层的节点频率。
   • 然后，在相同层级，比较原始树和参照树中节点的数量，消除相同的部分（即减去参照树中节点的数量）。
   • 统计原始树中剩余有效节点的频率。
   • 最后，按照频率降序排序，若频率相同，则按节点值降序输出。
3. 关键点：
   • 使用 unordered_map 来统计每层节点的频率。
   • 利用 vector 存储每一层的 unordered_map，方便访问和处理。
   • 排序时需要按照频率排序，频率相同则按值大小排序。

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁 立即订阅。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏