Ý tưởng 1

Gọi ~cnt_i~ là đếm số node và lá có độ cao là i

Dễ thấy với từng ~i~ độ cao muốn nó thành một cây nhị phân đầy đủ thì số lượng node và lá có độ cao là ~i~ đều phải là một số chẵn, để đếm số lượng node và lá có độ cao là ~i~ thì ta có các nhận xét như sau:

• Tổng số lượng node có độ cao ~i~ bằng tổng số node và lá có độ cao là ~i+1~ chia cho ~2~ hay ~\frac{cnt_{i+1}}{2}~

Vậy ta chỉ cần duyệt ngược lại từ độ cao cao nhất về độ cao là ~1~, mỗi lần duyệt ta kiểm tra xem với độ cao ~i~ có số lượng node và lá là ~cnt_i~ thì nó có thỏa mãn là cây nhị phân không khi và chỉ khi ~cnt_i~ là một số chẵn và nếu thỏa mãn thì ta cập nhật số lượng node và lá cho độ cao ~i-1~

Lưu ý: Ta cần phải xét xem số lượng gốc của cây hay là ~cnt_0~ có thỏa mãn luôn luôn bằng ~1~, nếu thỏa mãn cùng với điều kiện trên thì đây là cây nhị phân đầy đủ.

Ý tưởng 2

Sử dụng hàng đợi ưu tiên - priority queue để mô phỏng lại cách từ lá lên đỉnh gốc

Gọi ~pq~ là tập hợp độ cao của nút lá và phần tử đầu tiên của ~pq~ chính là nút lá có độ sâu cao nhất

Khi ~pq~ vẫn còn nhiều hơn ~1~ phần tử thì ta sẽ lấy trong ~pq~ hai phần tử mỗi lượt là:

• ~best~ là nút lá có độ cao cao nhất

• ~secondBest~ là nút lá có độ cao cao nhì ( tức có độ cao bé hơn hoặc bằng ~best~ )

Nếu ~best = secondBest~ thì ta sẽ thêm vào ~pq~ độ cao ~best-1~ ( hoặc ~secondBest-1~ ) và có khả năng tạo được cây nhị phân đày đủ, ngược lại không thể tạo được cây nhị phân đầy đủ

Vậy chạy đến khi ~pq~ chỉ còn ~1~ phần tử thì kiểm tra xem phần tử còn lại duy nhất trong ~pq~ đó có độ cao bằng ~0~ hay không, nếu không thì không thể tạo được cây nhị phân đầy đủ, ngược lại thì tạo được.

Code mẫu

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define nd second
#define st first
using namespace std;
const int N = 1e5 + 5;
int n, a[N];
void program(){
    cin >> n;
    map<int,int,greater<int> > m;
    for (int i = 1; i <= n; i++) cin >> a[i], m[a[i]]++;

    for (auto i : m){
        if (i.nd % 2 == 1 && i.st != 0){
            cout << "NO\n";
            return;
        }
        if (i.st == 0 && i.nd != 1){
            cout << "NO\n";
            return;
        } 
        if (i.st == 0 && i.nd == 1){
            break;
        }
        m[i.st - 1] += (i.nd / 2);
    }
    cout << "YES\n";
}
signed main(){
    ios;
    int test;
    cin >> test;
    while(test--) program();
}