C++で二分木がレベルごとにソートされているかどうかを判定する方法

この記事では、二分木（バイナリツリー）がレベルごとにソートされているかどうかを確認する方法を解説します。レベルごとにソートされた二分木とは、次のような構造を持つ木のことです。

各レベル内では、ノードが左から右に向かって昇順に並んでおり、さらに下のレベル（層）ほど、その上のレベルより大きな値を持つという特徴があります。

アルゴリズムの考え方

この問題は、レベル順走査（幅優先探索）を用いることで効率的に解決できます。手順は以下の通りです。

1. レベル順走査を実行しながら、現在のレベルの最小値と最大値を記録します。
2. 別の変数 prevMax を用意し、直前のレベルの最大値を保持します。
3. 現在のレベルの最小値と prevMax を比較します。最小値が prevMax より大きければ、木はそこまでのレベルで正しくソートされていることになります。
4. 比較後、prevMax を現在のレベルの最大値で更新し、次のレベルへ進みます。
5. すべてのレベルの走査が完了するまでこの処理を繰り返します。

途中で「現在のレベルの最小値 ≤ 前のレベルの最大値」となる箇所が見つかった場合は、その時点で false を返し、木はレベルごとにソートされていないと判定できます。

C++での実装例

#include <iostream>
#include <queue>
using namespace std;
class Node {
    public:
    int key;
    Node *left, *right;
};
Node* getNode(int key) {
    Node* newNode = new Node;
    newNode->key = key;
    newNode->left = newNode->right = NULL;
    return newNode;
}
bool isLevelWiseSorted(Node* root) {
    int prevMax = INT_MIN;
    int min_val, max_val;
    int levelSize;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        levelSize = q.size();
        min_val = INT_MAX;
        max_val = INT_MIN;
        while (levelSize > 0) {
            root = q.front();
            q.pop();
            levelSize--;
            min_val = min(min_val, root->key);
            max_val = max(max_val, root->key);
            if (root->left)
            q.push(root->left);
            if (root->right)
            q.push(root->right);
        }
        if (min_val <= prevMax)
            return false;
        prevMax = max_val;
    }
    return true;
}
int main() {
    Node* root = getNode(1);
    root->left = getNode(2);
    root->right = getNode(3);
    root->left->left = getNode(4);
    root->left->right = getNode(5);
    root->right->left = getNode(6);
    root->right->right = getNode(7);
    if (isLevelWiseSorted(root))
        cout << "Tree is levelwise Sorted";
    else
        cout << "Tree is Not levelwise sorted";
}

実行結果

Tree is level wise Sorted

コードのポイント

この実装では、キュー（std::queue）を使用してレベル順走査を実現しています。各ループの開始時にキューに入っている要素数（levelSize）を取得することで、「同じレベルのノードだけをまとめて処理する」ことが可能になります。計算量はノード数を N とした場合 O(N)、空間計算量も最悪ケースで O(N) となり、非常に効率的なアルゴリズムです。