完全二叉树层序排序去重输出问题及代码超限错误排查

问题背景 #

你需要实现一个功能：给定存储完全二叉树N个节点层序遍历数据的数组，按层输出排序后的遍历结果，且每层仅输出不同元素。但当前代码运行时提示OUTPUT LIMIT EXCEEDED!!!，以下是你的输入输出示例和代码：

输入示例

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

输出示例

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

错误代码

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
 //code
int t;
cin>>t;
while(t--) {
priority_queue<int,vector<int>,greater<int>> m;
int a;
cin>>a;
int k=1;
int arr[a];
queue<int> s;
for(int i=0;i<a;i++) {
cin>>arr[i];
s.push(arr[i]);
}
while(s.empty()==false) {
if(m.size()==k) {
while(m.empty()==false) {
cout<<m.top()<<" ";
}
k=k*2;
cout<<endl;
}else {
m.push(s.front());
s.pop();
}
}
if(m.empty()==false) {
while(m.empty()==false) {
cout<<m.top()<<" ";
}
cout<<endl;
}
}
return 0; 
}

问题排查与分析 #

导致OUTPUT LIMIT EXCEEDED的核心原因是死循环输出，同时代码还存在其他不符合需求的问题，逐一拆解：

1. 死循环输出：未清空优先队列
   当你输出优先队列m的元素时，只调用了m.top()获取元素，但没有调用m.pop()移除元素。这导致m永远不会为空，下一次循环又会进入输出逻辑，无限重复输出同一个元素，最终触发输出超限。

2. 未处理每层去重的需求
   题目要求每层仅输出不同元素，但当前代码的优先队列会存储所有层内元素（包括重复值），输出时会重复打印相同元素，不符合要求。

3. 变长数组（VLA）的未定义行为
   int arr[a];是C风格的变长数组，C++标准并不支持这种写法，部分编译器可能允许但属于未定义行为，容易导致内存问题。

4. 每层节点数计算逻辑错误
   完全二叉树的最后一层节点数可能不足2^(层号-1)，但代码中固定将k翻倍，会导致最后一层的元素一直无法触发输出，只能在循环结束后统一输出，虽然这不会直接导致超限，但逻辑不符合完全二叉树的层划分规则。

修正后的代码 #

以下是修复所有问题后的代码，我会标注关键修改点：

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        queue<int> q;
        // 用vector替代变长数组，符合C++标准
        vector<int> arr(n);
        for (int i = 0; i < n; ++i) {
            cin >> arr[i];
            q.push(arr[i]);
        }

        int level = 0;
        while (!q.empty()) {
            // 计算当前层的节点数：第一层1个，第二层2个，以此类推，最后一层取剩余节点数
            int level_size = min((1 << level), (int)q.size());
            // 使用set自动去重并排序（升序）
            set<int> unique_sorted;

            for (int i = 0; i < level_size; ++i) {
                unique_sorted.insert(q.front());
                q.pop();
            }

            // 输出当前层的去重排序结果
            for (auto it = unique_sorted.begin(); it != unique_sorted.end(); ++it) {
                if (it != unique_sorted.begin()) cout << " ";
                cout << *it;
            }
            cout << " ";
        }
        cout << endl;
    }
    return 0;
}

关键修改说明

• 替换变长数组为vector：避免未定义行为，符合C++标准。
• 用set实现去重+排序：set会自动对插入的元素进行排序并去重，完美满足每层输出不同且排序的需求。
• 正确计算每层节点数：用1 << level计算当前层理论节点数，同时和队列剩余节点数取最小值，处理最后一层节点不足的情况。
• 避免死循环：每次处理完一层后，队列的元素会被弹出，不会出现无限输出的情况。

验证输出 #

对于输入示例，修正后的代码会输出：

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

和题目给出的输出示例一致，同时不会出现输出超限的问题。

内容的提问来源于stack exchange，提问作者user12552749