C++で単一のキューを使って二分木をジグザグ（鋸歯状）レベル順に走査する方法

この問題では、二分木が与えられ、その木をジグザグ（鋸歯状）レベル順で走査して出力することが求められます。ポイントは、この走査をたった1つのキューだけを使って実現することです。

問題の例

まず、具体例で問題を理解しましょう。以下のような二分木を考えます。

出力：

3     1     7     2     8     9     5

ご覧のとおり、第1レベルは左から右へ、第2レベルは右から左へ、第3レベルは再び左から右へと、レベルごとに方向を交互に入れ替えながらノードを出力しています。

解決アプローチ：単一キュー＋区切りフラグ

通常、ジグザグ走査には2つのスタックや双方向キュー（deque）を使う方法が知られていますが、ここでは単一のキューだけで実装します。

そのために活用するのが、次の2つの仕組みです。

• 区切りフラグ（NULLセンチネル）： レベルの境界を示すために、キューの中にNULLを挿入します。
• 方向フラグ： 現在のレベルを出力する方向（左→右 または 右→左）を管理するカウンターです。

アルゴリズムの流れは以下のとおりです。

1. ルート要素をキューに挿入し、その前後にNULLを配置します。
2. キューから要素を取り出しながら、その子ノードを順次キューへ挿入していきます。
3. NULLに到達したら、それがレベルの終わりを意味するため、方向フラグを確認し、指定された方向に沿ってそのレベルの要素を出力します。
4. 最後のNULLに到達するまで、この処理を繰り返します。

つまり、キュー内のNULLが「レベルの区切り」の役割を果たし、各レベルの要素範囲を前後から走査できるため、単一のキューでもジグザグ出力が可能になるのです。

C++実装例

上記の解法を実装したプログラムがこちらです。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node *left, *right;
};
struct Node* insertNode(int data) {
    struct Node* node = new struct Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
void zigZagTraversal(struct Node* root, int n){
    struct Node* queue[2 * n];
    int top = -1;
    int front = 1;
    queue[++top] = NULL;
    queue[++top] = root;
    queue[++top] = NULL;
    int prevFront = 0, count = 1;
    while (1) {
        struct Node* curr = queue[front];
        if (curr == NULL) {
            if (front == top)
                break;
            else {
                if (count % 2 == 0) {
                    for (int i = prevFront + 1; i < front; i++)
                        cout<<queue[i]->data<<"\t";
                }
                else {
                    for (int i = front - 1; i > prevFront; i--)
                        cout<<queue[i]->data<<"\t";
                }
                prevFront = front;
                count++;
                front++;
                queue[++top] = NULL;
                continue;
            }
        }
        if (curr->left != NULL)
            queue[++top] = curr->left;
        if (curr->right != NULL)
            queue[++top] = curr->right;
        front++;
    }
    if (count % 2 == 0) {
        for (int i = prevFront + 1; i < top; i++)
            cout<<queue[i]->data<<"\t";
    }
    else {
        for (int i = top - 1; i > prevFront; i--)
            cout<<queue[i]->data<<"\t";
    }
}
int main() {
    struct Node* root = insertNode(3);
    root->left = insertNode(1);
    root->right = insertNode(7);
    root->left->left = insertNode(5);
    root->left->right = insertNode(9);
    root->right->left = insertNode(8);
    root->right->right = insertNode(2);
    cout<<"Zig Zag traversal of the tree is :\n";
    zigZagTraversal(root, 7);
    return 0;
}

実行結果

Zig Zag traversal of the tree is :
3     1     7     2     8     9     5

コードのポイント解説

• キューの初期化： NULL → ルート → NULL の順で挿入し、最初と最後に区切りを用意します。
• レベルの出力： カウンターcountが偶数なら左から右へ、奇数なら右から左へと、prevFrontからfrontまでの範囲を逆順・順序どおりに出力します。
• 終了条件： frontがtopと一致したとき、すべてのレベルの走査が完了したことを意味します。

この手法により、余分なデータ構造を追加することなく、時間計算量 O(n)・空間計算量 O(n) でジグザグレベル順走査を実現できます。