Kiểm tra cây nhị phân hoàn chỉnh trong C++

Cho một cây nhị phân, kiểm tra xem nó có phải cây nhị phân hoàn chỉnh (complete binary tree) hay không. Cây nhị phân hoàn chỉnh cấp n có n-1 cấp hoàn chỉnh, và tất cả nút ở cấp n được điền từ trái sang phải. Ví dụ cây đầu vào cho kết quả true.

Giải thuật

• Nếu cây rỗng trả về true.
• Tạo hàng đợi q, đưa gốc vào.
• flag := true.
• Khi q không rỗng:
  • sz := q.size()
  • Khi sz > 0:
    • Lấy nút node từ hàng đợi.
    • Nếu node->left tồn tại:
      • Nếu flag true thì đưa con trái vào hàng đợi, ngược lại trả về false.
    • Ngược lại flag := false.
    • Nếu node->right tồn tại:
      • Nếu flag true thì đưa con phải vào hàng đợi, ngược lại trả về false.
    • flag := false.
    • sz--
• Trả về true.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = NULL; right = NULL; }
};

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        if (!root) return true;
        queue<TreeNode*> q;
        q.push(root);
        bool isComplete = true;
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                TreeNode* node = q.front(); q.pop();
                if (node->left) {
                    if (isComplete) q.push(node->left);
                    else return false;
                } else isComplete = false;
                if (node->right) {
                    if (isComplete) q.push(node->right);
                    else return false;
                } else isComplete = false;
            }
        }
        return true;
    }
};

Đầu vào

{1,2,3,4,5,6}

Đầu ra

1